#include<iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<map>

#include<queue>

#include<vector>

#include<cmath>

#include<stdlib.h>

#include<time.h>

#include<stack>

#include<set>

using namespace std;

#define rep0(i,l,r) for(int i = (l);i < (r);i++)

#define rep1(i,l,r) for(int i = (l);i <= (r);i++)

#define rep_0(i,r,l) for(int i = (r);i > (l);i--)

#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

#define MS0(a) memset(a,0,sizeof(a))

#define MS1(a) memset(a,-1,sizeof(a))

#define inf 0x3f3f3f3f

#define lson l, m, rt << 1

#define rson m+1, r, rt << 1|1

//typedef __int64 ll;

template<typename T>

void read1(T &m)

{

    T x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    m = x*f;

}

template<typename T>

void read2(T &a,T &b){read1(a);read1(b);}

template<typename T>

void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

template<typename T>

void out(T a)

{

    if(a>) out(a/);

    putchar(a%+'');

}

const int maxl = ;

const int ten[]={,,,,};

struct Biginter{

    int d[maxl]; // 最大数位只取四位，因为相乘不会爆int~~,并且每次构造对象时d[]一定要为0；

    Biginter(char *s){

        int len = strlen(s);

        d[] = (len-)/+;//每一个数组里面存四位，并且d[0]记录的是最多总的位数(下标)

        int i,j,k;

        for(i = ;i <= d[];i++) d[i] = ;

        for(i = len-;i >= ;i--){

            j = (len--i)/+; //保存的下标;

            k = (len--i)%;//在每一个下标保存中仍然要保存顺序;

            d[j] += ten[k]*(s[i]-'');

        }

        while(d[] >  && d[d[]] == ) d[]--;    //可能就为0;

    }

    Biginter(){MS0(d);}//手动初始化为0

    void tostring(){  //输出后换行

        out(d[d[]]);

        for(int i = d[]-;i > ;i--){

            printf("%04d",d[i]);

        }

        puts("");

    }

};

bool operator <(const Biginter& a,const Biginter& b)

{

    if(a.d[] != b.d[]) return a.d[] < b.d[];

    for(int i = a.d[];i >= ;i--){

        if(a.d[i] != b.d[i]) return a.d[i] < b.d[i];

    }

    return false;// a== b

}

bool operator ==(const Biginter& a,const Biginter& b)

{

    if(a.d[] != b.d[]) return false;

    for(int i = a.d[];i >= ;i--){

        if(a.d[i] != b.d[i]) return false;

    }

    return true;

}

Biginter operator +(const Biginter& a,const Biginter& b)

{

    Biginter c;

    c.d[] = max(a.d[],b.d[]);

    for(int i = ;i <= c.d[];i++){

        c.d[i] += a.d[i]+b.d[i];

        if(c.d[i] >= ten[]){//其实每次只需要看是否要进1即可;

            c.d[i] -= ten[],c.d[i+]++;

            if(i == c.d[]){

                ++c.d[];

                break;

            }

        }

    }

    return c;

}

Biginter operator -(const Biginter& a,const Biginter& b){

    Biginter c;

    c.d[] = a.d[];

    for(int i = ;i <= c.d[];i++){

        c.d[i] += a.d[i] - b.d[i];

        if(c.d[i] < ){

            c.d[i] += ten[];

            c.d[i+]--;

        }

    }

    while(c.d[] >  && c.d[c.d[]] == ) c.d[]--;

    return c;

}

Biginter operator *(const Biginter& a,const Biginter& b)

{

    Biginter c;

    c.d[] = a.d[]+b.d[];

    for(int i = ;i <= a.d[];i++){

        int x = ;

        for(int j = ;j <= b.d[];j++){

            x += a.d[i]*b.d[j]+c.d[i+j-];

            c.d[i+j-] = x%ten[];//相乘时需要记录超出多少需要mod，但相加减时超出数值就是1~~不用mod更快

            x /= ten[];

        }

        c.d[i+b.d[]] = x;//***

    }

    while(c.d[] >  && c.d[c.d[]] == ) c.d[]--;

    return c;

}

int main()

{

    Biginter F[]={"","",""},F3(""),F2("");

    rep1(i,,)

        F[i] = F[i-]*F3 - F[i-] + F2;

    int n;

    while(scanf("%d",&n) == ){

        F[n].tostring();

    }

    return ;

}