#include <cstdio>
#define mod 666013
using namespace std;
int k,bit[50],n;
long long a[5][5],mat[5][5];
void base_2()
{
while(n>0)
    {
    bit[++k]=n%2; n/=2;
    }
}
int main()
{
long long x,y,z,q,x1,y1,z1,q1;
int i;
freopen("kfib.in","r",stdin); scanf("%d",&n); fclose(stdin);
a[1][1]=0; a[1][2]=1; a[2][1]=1; a[2][2]=1;
mat[1][1]=1; mat[1][2]=0; mat[2][1]=0; mat[2][2]=1;
k=0;
--n;
base_2();
for(i=k;i>=1;--i)
    {
    x=((mat[1][1]*mat[1][1])%mod+(mat[1][2]*mat[2][1])%mod)%mod;
    y=((mat[1][1]*mat[1][2])%mod+(mat[1][2]*mat[2][2])%mod)%mod;
    z=((mat[2][1]*mat[1][1])%mod+(mat[2][2]*mat[2][1])%mod)%mod;
    q=((mat[2][1]*mat[1][2])%mod+(mat[2][2]*mat[2][2])%mod)%mod;
    if(bit[i]==1)
            {
            x1=((x*a[1][1])%mod+(y*a[2][1])%mod)%mod;
            y1=((x*a[1][2])%mod+(y*a[2][2])%mod)%mod;
            z1=((z*a[1][1])%mod+(q*a[2][1])%mod)%mod;
            q1=((z*a[1][2])%mod+(q*a[2][2])%mod)%mod;
            mat[1][1]=x1; mat[1][2]=y1; mat[2][1]=z1; mat[2][2]=q1;
            }
        else {
             mat[1][1]=x; mat[1][2]=y; mat[2][1]=z; mat[2][2]=q;
             }
    }
freopen("kfib.out","w",stdout); printf("%lld",mat[2][2]); fclose(stdout);
return 0;
}