#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

int a[3][3],b[3][3],c[3][3],sol[3][3];

inline void Copy(int a[][3], int b[][3])
{
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j) a[i][j]=b[i][j];
}

inline void Mult_Mat(int a[][3], int b[][3])
{
    int i,j,k;
    for(i=1;i<=2;++i)
        for(j=1;j<=2;++j)
        {
            c[i][j]=0;
            for(k=1;k<=2;++k) c[i][j]=(1LL*c[i][j] + 1LL*a[i][k]*b[k][j])%MOD;
        }

    Copy(a,c);
}

inline void Pow_Log(int a[][3], int p)
{
    int i;
    for(i=1;i<=2;++i) sol[i][i]=1;
    while(p)
    {
        if(p&1)
        {
            Mult_Mat(sol,a); --p;
        }
        Mult_Mat(a,a); p>>=1;
    }
    Copy(a,sol);
}

int main()
{
    int n;
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    cin>>n;
    if(!n) cout<<"0\n";
    if(n==1) cout<<"1\n";
    if(n>1)
    {
        a[1][1]=0; a[1][2]=1;
        a[2][1]=1; a[2][2]=1;
        Pow_Log(a,n-1);
        b[1][1]=0; b[1][2]=1;
        Mult_Mat(b,a);
        cout<<b[1][2]<<"\n";
    }
    return 0;
}