// PR Bab 06, tantangan: Fibonacci dengan ingatan (memoization).
//
// Versi di bawah lambat karena menghitung ulang hal yang sama.
// Tambahkan array global long long ingat[100] berisi -1:
//   - sebelum menghitung, periksa apakah jawabannya sudah ada,
//   - sesudah menghitung, simpan ke sana.
// Bandingkan waktu fib(45) sebelum dan sesudah perubahan.
//
// Compile:  g++ -std=c++17 -O2 -o fibingat exercises/06/homework/05-fib-ingat.cpp
// Jalankan: ./fibingat

#include <iostream>
using namespace std;

// Tulis array ingatanmu di sini:

long long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

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