#include <bits/stdc++.h>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int n;
const int mod=666013;
struct mat
{
    int a[3][3];
    mat()
    {
        memset(a,0,sizeof(a));
    }
};
mat produs(mat A,mat B)
{
    mat ans;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
          for(int k=0;k<2;k++)
             ans.a[i][j]=(ans.a[i][j]+1LL*A.a[i][k]*B.a[k][j])%mod;
    return ans;
}
mat lgp(mat A,int p)
{
    mat ans;
    ans.a[0][0]=ans.a[1][1]=1;
    while(p)
    {
        if(p&1)
        {
            ans=produs(ans,A);
            p--;
        }
        p>>=1;
        A=produs(A,A);
    }
    return ans;
}
mat M,sol;
int main()
{
    in>>n;
    M.a[0][0]=M.a[0][1]=M.a[1][0]=1;
    sol.a[0][0]=sol.a[1][0]=1;
    if(n<=2) out<<1;
    else
    {
        M=lgp(M,n-2);
        sol=produs(M,sol);
        out<<sol.a[0][0];
    }
    return 0;
}