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

int main()
{
    ifstream in("nunta.in");
    ofstream out("nunta.out");
    int n;
    in>>n;
    int i,j,t;
    char a[200],b[200],c[200];
    for(i=0;i<200;i++)
        {
            a[i]=0;
            b[i]=0;
            c[i]=0;
        }
    a[0]=1;
    b[0]=2;
    for(i=3;i<=n;i++)
        {
            for(j=0;j<200;j++)
                {
                    c[j]=a[j];
                    a[j]=b[j];
                }
            t=0;
            for(j=0;j<200;j++)
                {
                    b[j]=b[j]+c[j]+t;
                    if(b[j]>9)
                        {
                            t=1;
                            b[j]=10-b[j];
                        }
                }
        }
    int jj=199;
    while(b[jj]==0)
        {
            jj--;
        }
    for(;jj>=0;jj--)
        {
            out<<(char)(b[jj]+48)<<"\n";
        }
    return 0;
}