///circular
//unordered_
#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long n,fib[4][4],f[4][4];
long long ras[4][4];
void inmul(long long a[][4],long long b[][4])
{
    int i,j,y;
    long long c[4][4];
    c[1][1]=c[1][2]=c[2][2]=c[2][1]=0;
    for(i=1; i<=2; i++)
        for(j=1; j<=2; j++)
            for(y=1; y<=2; y++)
                c[i][j]=(c[i][j]+a[i][y]*b[y][j])%MOD;
    for(i=1; i<=2; i++)
        for(j=1; j<=2; j++)
            a[i][j]=c[i][j];
    return;
}
void ridic(long long nr[][4],int put)
{
    ras[1][2]=0;
    ras[2][1]=0;
    ras[1][1]=ras[2][2]=1;
    while(put)
    {
        if(put%2==1)
            inmul(ras,nr);
        put/=2;
        inmul(nr,nr);
    }
    return;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    fin>>n;
    fib[1][2]=fib[2][1]=fib[2][2]=1;
    ridic(fib,n-1);
    //cout<<ras[1][1]<<" "<<ras[1][2]<<'\n'<<ras[2][1]<<" "<<ras[2][2];
    fout<<ras[2][2];
    return 0;
}