#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
ll n,mod=666013, I[2][2] = {{1, 0}, {0, 1}},a[2][2] = {{1, 1}, {1, 0}};
void mult(ll a[2][2],ll b[2][2]){
    ll c[2][2];
    for(ll i=0;i<2;i++)
    for(ll j=0;j<2;j++)
        c[i][j]=0;
for(ll i=0;i<2;i++)
    for(ll j=0;j<2;j++)
    for(ll k=0;k<2;k++)
    {c[i][j]+=(a[i][k]*b[k][j])%mod;
    c[i][j]%=mod;}
 for(ll i=0;i<2;i++)
    for(ll j=0;j<2;j++)
        a[i][j]=c[i][j];
}
void put( ll t){
while(t>0){
    if(t%2==0)
{
    mult(a,a);
    t/=2;
}
else{
    mult(I,a);
    t--;
}
}
}
int main()
{
    fin>>n;
if(n<=1) fout<<n;else{
put(n-1);
fout<<I[0][0];
}
    return 0;
}