#include <fstream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int n, i, j, a[2][2], p[2][2], mod=666013, ans[2][2];
void matrice(int a[2][2], int b[2][2])
{
    int c[2][2];
    c[0][1]=c[0][0]=c[1][0]=c[1][1]=0;
    c[0][0]=((1ll*a[0][0]*b[0][0])%mod+(1ll*a[0][1]*b[1][0])%mod)%mod;
    c[0][1]=((1ll*a[0][0]*b[0][1])%mod+(1ll*a[0][1]*b[1][1])%mod)%mod;
    c[1][0]=((1ll*a[1][0]*b[0][0])%mod+(1ll*a[1][1]*b[1][0])%mod)%mod;
    c[1][1]=((1ll*a[1][0]*b[0][1])%mod+(1ll*a[1][1]*b[1][1])%mod)%mod;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
        a[i][j]=c[i][j]%mod;
}
void explog(int n)
{
    while(n)
    {
        if(n%2==1)
            matrice(p, a);
        matrice(a, a);
        n/=2;
    }
}
int main()
{
    fin>>n;
    //a[0][1]=a[1][0]=a[1][1]=1;
   // p[0][1]=p[1][0]=p[1][1]=1;
   p[0][0]=p[1][1]=1;
   a[0][1]=a[1][1]=a[1][0]=1;
    explog(n-2);
    ans[0][0]=1;
    ans[0][1]=1;
    matrice(ans, p);
    fout<<ans[0][1];

    return 0;
}