#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
unordered_map<int, long long> fib_cache;
 
long long fibonacci(int n) {
    if (n <= 1) return 1;
    if (fib_cache.find(n) != fib_cache.end()) return fib_cache[n];
    fib_cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return fib_cache[n];
}
 
// Why naive recursion fails for n=40/50:
// - Time complexity: O(2^n) - exponentially slow
// - Stack overflow risk
// Memoization reduces this to O(n) time and space
void solve() {
     cout << fibonacci(10) << endl;
}
 
int main() {
    IOS;
    solve();
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgSU9TIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7Y2luLnRpZSgwKTtjb3V0LnRpZSgwKTsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdW5vcmRlcmVkX21hcDxpbnQsIGxvbmcgbG9uZz4gZmliX2NhY2hlOwoKbG9uZyBsb25nIGZpYm9uYWNjaShpbnQgbikgewogICAgaWYgKG4gPD0gMSkgcmV0dXJuIDE7CiAgICBpZiAoZmliX2NhY2hlLmZpbmQobikgIT0gZmliX2NhY2hlLmVuZCgpKSByZXR1cm4gZmliX2NhY2hlW25dOwogICAgZmliX2NhY2hlW25dID0gZmlib25hY2NpKG4gLSAxKSArIGZpYm9uYWNjaShuIC0gMik7CiAgICByZXR1cm4gZmliX2NhY2hlW25dOwp9CgovLyBXaHkgbmFpdmUgcmVjdXJzaW9uIGZhaWxzIGZvciBuPTQwLzUwOgovLyAtIFRpbWUgY29tcGxleGl0eTogTygyXm4pIC0gZXhwb25lbnRpYWxseSBzbG93Ci8vIC0gU3RhY2sgb3ZlcmZsb3cgcmlzawovLyBNZW1vaXphdGlvbiByZWR1Y2VzIHRoaXMgdG8gTyhuKSB0aW1lIGFuZCBzcGFjZQp2b2lkIHNvbHZlKCkgewogICAgIGNvdXQgPDwgZmlib25hY2NpKDEwKSA8PCBlbmRsOwp9CgppbnQgbWFpbigpIHsKICAgIElPUzsKICAgIHNvbHZlKCk7CiAgICByZXR1cm4gMDsKfQ==