#include <iostream>
#include <cstring>
using namespace std;
 
// Function to find nth Fibonacci number
int fib(int n, int lookup[])
{
    if (n <= 1)
        return n;
 
    // if sub-problem is seen for the first time
    if (lookup[n] == 0)
        lookup[n] = fib(n - 1, lookup) + fib(n - 2, lookup);
 
    return lookup[n];
}
 
int main() 
{
	int n = 8;
    int lookup[n + 1];
 
 	memset(lookup, 0, sizeof(lookup));
 
    cout << fib(n, lookup);
 
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAovLyBGdW5jdGlvbiB0byBmaW5kIG50aCBGaWJvbmFjY2kgbnVtYmVyCmludCBmaWIoaW50IG4sIGludCBsb29rdXBbXSkKewogICAgaWYgKG4gPD0gMSkKICAgICAgICByZXR1cm4gbjsKICAgIAogICAgLy8gaWYgc3ViLXByb2JsZW0gaXMgc2VlbiBmb3IgdGhlIGZpcnN0IHRpbWUKICAgIGlmIChsb29rdXBbbl0gPT0gMCkKICAgICAgICBsb29rdXBbbl0gPSBmaWIobiAtIDEsIGxvb2t1cCkgKyBmaWIobiAtIDIsIGxvb2t1cCk7CiAgICAgCiAgICByZXR1cm4gbG9va3VwW25dOwp9CiAKaW50IG1haW4oKSAKewoJaW50IG4gPSA4OwogICAgaW50IGxvb2t1cFtuICsgMV07CiAKIAltZW1zZXQobG9va3VwLCAwLCBzaXplb2YobG9va3VwKSk7CgogICAgY291dCA8PCBmaWIobiwgbG9va3VwKTsKIAogICAgcmV0dXJuIDA7Cn0K