//#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("kfib.in");
ofstream cout ("kfib.out");

struct matrix
{
    int a,b,c,d;
};
matrix z,x;
long long n,i,j;

matrix matrixszorz (matrix x, matrix y)
{
    int a,b,c,d;
    a=x.a*y.a+x.b*y.c;
    b=x.a*y.b+x.b*y.d;
    c=x.c*y.a+x.d*y.c;
    d=x.c*y.b+x.d*y.d;
    return {a,b,c,d};
}

matrix hat (matrix x, int n)
{
    matrix k,y;
    if(n==0) return {1,0,0,1};
    else if (n==1) return {1,1,1,0};
        else
        {
            k=hat(x,n/2);
            if (n%2==0) return matrixszorz(k,k);
            else
            {
                y=matrixszorz(k,k);
                return matrixszorz(y,x);
            }
        }

}
int main()
{
    x.a=1;
    x.b=1;
    x.c=1;
    x.d=0;
    z=hat(x,6);
    cout<<z.b<<"\n";
    return 0;
}