代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, dp[5005][1005], l;
void add(int x) {
	for(int i = 1; i <= l; ++i) {
		dp[x][i] = dp[x - 1][i] + dp[x - 2][i];
	}
	for(int i = 1; i <= l; ++i) {
		if(dp[x][i] >= 10) {
			dp[x][i + 1] += dp[x][i] / 10;
			dp[x][i] %= 10;
			if(dp[x][l + 1] > 0) l++;
		}
	}
}
signed main() {
	cin >> n;
	dp[1][1] = 1, dp[2][1] = 2; l = 1;
	for(int i = 3; i <= n; ++i) add(i);
	for(int i = l; i >= 1; --i) cout << dp[n][i]; cout << endl;
	return 0;
}