#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in ("kfib.in");
ofstream out ("kfib.out");
const int mod=666013;
long long rez[4][4],put[4][4],v[15],cur[4][4];
int main()
{
    long long i,n;
    cin>>n;
    if(n<=5)
    {
        v[0]=0;
        v[1]=1;
        for(i=2;i<=n;++i)
            v[i]=v[i-1]+v[i-2];
        cout<<v[n];
        return 0;
    }
    n-=3;
    put[1][1]=rez[1][1]=0;
    put[2][1]=rez[2][1]=1;
    put[1][2]=rez[1][2]=1;
    put[2][2]=rez[2][2]=1;
    while(n)
    {
        if(n&1)
        {
            cur[1][1]=(rez[1][1]*1LL*put[1][1]%mod+rez[1][2]*put[2][1]%mod)%mod;
            cur[1][2]=(rez[1][1]*1LL*put[1][2]%mod+rez[1][2]*put[2][2]%mod)%mod;
            cur[2][1]=(rez[2][1]*1LL*put[1][1]%mod+rez[2][2]*put[2][1]%mod)%mod;
            cur[2][2]=(rez[2][1]*1LL*put[1][2]%mod+rez[2][2]*put[2][2]%mod)%mod;
            rez[1][1]=cur[1][1];
            rez[2][2]=cur[2][2];
            rez[1][2]=cur[1][2];
            rez[2][1]=cur[2][1];
            --n;
        }
        else
        {
            cur[1][1]=(put[1][1]*1LL*put[1][1]%mod+put[1][2]*put[2][1]%mod)%mod;
            cur[1][2]=(put[1][1]*1LL*put[1][2]%mod+put[1][2]*put[2][2]%mod)%mod;
            cur[2][1]=(put[2][1]*1LL*put[1][1]%mod+put[2][2]*put[2][1]%mod)%mod;
            cur[2][2]=(put[2][1]*1LL*put[1][2]%mod+put[2][2]*put[2][2]%mod)%mod;
            put[1][1]=cur[1][1];
            put[2][2]=cur[2][2];
            put[1][2]=cur[1][2];
            put[2][1]=cur[2][1];
            n>>=1;
        }
    }
    cout<<(rez[1][2]+rez[2][2])%mod;
}