#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define MOD 666013



ifstream fin("kfib.in"); ofstream fout("kfib.out");

int k;
ll z[2][2];


void multiply(ll a[2][2], ll b[2][2], ll c[2][2]){

c[0][0]=((((a[0][0]%MOD)*(b[0][0]%MOD))%MOD)+(((a[0][1]%MOD)*(b[1][0]%MOD))%MOD))%MOD;
c[0][1]=( ( (a[0][0]%MOD)*(b[1][0])%MOD )%MOD+((a[0][1]%MOD)*(b[1][1]%MOD))%MOD )%MOD;
c[1][0]=( ((a[1][0]%MOD)*(b[0][0]%MOD))%MOD+( (a[1][1]%MOD)*(b[1][0])%MOD )%MOD )%MOD;
c[1][1]=( ((a[1][0]%MOD)*(b[0][1]%MOD) )%MOD+((a[1][1]%MOD)*(b[1][1]%MOD) )%MOD )%MOD;

}


ll a[2][2], s[2][2];


void logp(ll b[2][2], ll e){
ll rez[2][2];

if(e==1){ a[0][0]=b[0][0]; a[0][1]=b[0][1]; a[1][0]=b[1][0]; a[1][1]=b[1][1]; s[0][0]=b[0][0]; s[0][1]=b[0][1]; s[1][0]=b[1][0]; s[1][1]=b[1][1];    return; }


if(e%2==0){
    multiply(b, b, rez); logp( rez,  e/2);    return ;
}
else{
    multiply(b, b, rez); logp( rez, (e-1)/2); multiply(b, a, s); a[0][0]=s[0][0]; a[0][1]=s[0][1]; a[1][0]=s[1][0]; a[1][1]=s[1][1];  return;
}

}





int main(){
fin>>k;

z[0][0]=0; z[0][1]=1;
z[1][0]=1; z[1][1]=1;


if(k==0){return fout<<0, 0; }


logp(z, k);

ll f[2][2];

a[0][0]=0; a[0][1]=1;

a[1][0]=0; a[1][1]=0;
for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
        cout<<s[i][j]<<" ";
    }
    cout<<"\n";
}
multiply(a, s , f);

fout<<f[0][0];
return 0;
}