fibnachi

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int M_S = 45;
vector<int>ans(M_S, -1);
int fib(int n){
    if (ans[n]!=-1){
        return ans[n];
    }
    if (n<=1){
        ans[n]=1;
    }
    else{
        ans[n]=fib(n-1)+fib(n-2);
    }
    return ans[n];
}

int main() {
    int a;
    cin>>a;
    cout<<fib(a-1);
    cout<<"\n";
    return 0;
}