#include #include long long dp[51]; long long search(int i) { if (i == 0) return 1; if (i < 0) return 0; if (dp[i] != -1) return dp[i]; return dp[i] = search(i - 1) + search(i - 2); } int main() { int n; scanf("%d", &n); memset(dp, -1, sizeof(dp)); printf("%lld\n", search(n)); return 0; }