#include <bits/stdc++.h>
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define ll long long
#define forq(i,ii,n)for(i=ii;i<n;i++)
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
ll a[2][4]={{0,1,1,1},{0,1,1,1}},b[4]={0,1,1,1},i,j,n[63];bool x;
#define mul(q)a[!x][0]=a[!x][1]=a[!x][2]=a[!x][3]=0;\
a[!x][0]=(a[x][0]*q[0]+a[x][1]*q[2])%666013;\
a[!x][1]=(a[x][0]*q[1]+a[x][1]*q[3])%666013;\
a[!x][2]=(a[x][2]*q[0]+a[x][3]*q[2])%666013;\
a[!x][3]=(a[x][2]*q[1]+a[x][3]*q[3])%666013;\
x=!x;
int main()
{
in>>n[62];
for(i=62;n[i]!=1;)n[i-1]=n[i]/2,i--;
while(i<62)
{
    mul(a[x]);
    ++i;
    //cout<<n[i]<<' '<<a[x][1];
    if(n[i]%2)
       {mul(b);;}
    //cout<<'\n';
}
out<<a[x][1];
}