#include <cstdio>

using namespace std;

int mat[][2]={{0,1},{1,1}},rasp[][2]={{1,0},{0,1}};
int inmultire(int dest[2][2],int surs[2][2]);
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(;n>0;n>>=1)
    {
        if(1&n)
            inmultire(rasp,mat);
        inmultire(mat,mat);
    }
    printf("%d",rasp[0][1]);
    return 0;
}
int inmultire(int dest[2][2],int surs[2][2])
{
    long long x11,x21,x12,x22;
    x11=1ll*dest[0][0]*surs[0][0]+1ll*dest[0][1]*surs[1][0];
    x12=1ll*dest[0][0]*surs[0][1]+1ll*dest[0][1]*surs[1][1];
    x21=1ll*dest[1][0]*surs[0][0]+1ll*dest[1][1]*surs[1][0];
    x22=1ll*dest[1][0]*surs[0][1]+1ll*dest[1][1]*surs[1][1];
    dest[0][0]=x11%MOD;
    dest[0][1]=x12%MOD;
    dest[1][0]=x21%MOD;
    dest[1][1]=x22%MOD;
}