HDU 1568

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int fib[21] , i , n;
    fib[0] = 0 , fib[1] = 1;
    for(i=2;i<21;i++)    fib[i] = fib[i-1] + fib[i-2];
    
    while(scanf("%d",&n)!=EOF)
    {
        if(n<=20)
            printf("%d\n",fib[n]);
        else
        {
            double p = n * log10((1+sqrt(5.0))*0.5)-0.5*log10(5.0);
            p = p - int(p);
            int res = pow(10.0,p) * 1000;
            printf("%d\n",res);
        }
    }
    return 0;
}