#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int mod=666013;


int main()
{
    int k;
    fin>>k;
    int z[3][3], aux[3][3];
    z[1][1]=0; z[1][2]=1; z[2][1]=1; z[2][2]=1;

    for(int i=1; i<k-1; i++){
        aux[1][1]=z[1][1]; aux[1][2]=z[1][2]; aux[2][1]=z[2][1]; aux[2][2]=z[2][2];
        z[1][1]=aux[1][2]%mod;
        z[1][2]=(aux[1][1]+aux[1][2])%mod;
        z[2][1]=aux[2][2]%mod;
        z[2][2]=(aux[2][1]+aux[2][2])%mod;
    }
    fout<<z[2][2];
    return 0;
}