tijie<AC>

tijie<AC>

#include<bits/stdc++.h>
using namespace std;
string s[5010];
int a[2010], b[2010], c[2010];
string add(string sa, string sb) {
    int la = sa.size(), lb = sb.size(), lc = max(la, lb);
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    for (int i = 0; i < la; i++) a[i] = sa[la-i-1] - '0';
    for (int i = 0; i < lb; i++) b[i] = sb[lb-i-1] - '0';
    for (int i = 0; i < lc; i++) {
        c[i] += a[i] + b[i];
        c[i+1] = c[i] / 10;
        c[i] %= 10;
    }
    if (c[lc] > 0) lc++;
    string t = "";
    for (int i = lc - 1; i >= 0; i--) t += c[i] + '0';
    return t;
}
int main() {
	int n;
    cin >> n;
    s[1] = "1", s[2] = "2";
    for (int i = 3; i <= n; i++)
        s[i] = add(s[i-1], s[i-2]);
    cout << s[n];
    return 0;
}