#include<bits/stdc++.h>
using namespace std;


int n;

void solve()
{
    int pre1=2,pre2=1;
    int here;


    if(n==2)
        cout<<pre1;
    else if(n==1)
    {
        cout<<pre2;
    }
    else
    {
        for(int i=3; i<=n; i++)
        {
            int aux=here;
            here=pre1+pre2;

            pre2=pre1;
            pre1=here;
        }
        cout<<here<<endl;
    }
}



int main()
{

    cin>>n;
    solve();
}
---------------------

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

using namespace std;

ifstream in("cladire.in");
ofstream out("cladire.out");

int trepte[100000],n,k;
int main()
{
    cin>>n>>k;
    trepte[0]=1;
    for(int i=1; i<n; i++)
    {
        for(int p=1; p<=k && i-p>=0; p++)
        {
            trepte[i]+=trepte[i-p];
            trepte[i]%=9001;
        }
    }
    cout<<trepte[n-1];
    return 0;
}


----------------------


#include<bits/stdc++.h>
using namespace std;


ifstream in("sumtri.in");
ofstream out("sumtri.out");



int mat[101][101],n;
int sol[101][101];

void read()
{
    in>>n;
    for(int i=1; i<=n; i++)
    {
        for(int k=1; k<=i; k++)
        {
            in>>mat[i][k];
        }

    }

}
int solve()
{
    int a=0;
    for(int i=1; i<=n; i++)
    {
        for(int k=1; k<=i; k++)
        {
            sol[i][k]=max(sol[i-1][k],sol[i-1][k-1])+mat[i][k];
            a=max(a,sol[i][k]);
        }
    }

    return a;
}


int main()
{

    read();
    out<<solve();
    return 0;
}


------------------------


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

using namespace std;

ifstream in("cladire.in");
ofstream out("cladire.out");

int mat[1001][1001];
int startx,starty;

int res=0;
void read()
{
    in>>starty>>startx;
    for(int i=0; i<1001; i++)
        for(int k=0; k<1001; k++)
            mat[i][k]=1;
}
void solve()
{
    for(int i=1; i<starty; i++)
    {
        for(int k=1; k<startx; k++)
        {
            mat[i][k]=(mat[i-1][k]+mat[i][k-1])%9901;
        }
    }
    out<<mat[starty-1][startx-1];
}
int main()
{
    read();
    cout<<startx<<" "<<starty<<endl;
    solve();
    return 0;
}


-----------------------




#include<bits/stdc++.h>
using namespace std;


ifstream in("cladire3.in");
ofstream out("cladire3.out");

int m,n,mat[201][201],sum[201][201];


void read()
{
    in>>m>>n;
    for(int i=1; i<=m; i++)
    {
        for(int k=1; k<=n; k++)
        {
            in>>mat[i][k];
        }
    }
}


int solve()
{
    for(int i=1; i<=m; i++)
    {
        for(int k=n; k>=1; k--)
        {
            if(i==1)
            {
                sum[i][k]=sum[i][k+1]+mat[i][k];
            }
            else if(k==n)
            {
                sum[i][k]=sum[i-1][k]+mat[i][k];
            }
            else
                sum[i][k]=min(sum[i-1][k],sum[i][k+1])+mat[i][k];
        }
    }

    return sum[m][1];

}


int main()
{
    read();
    out<<solve();

}


---------------------