#include <iostream>
#include <fstream>
using namespace std;

long long init[][2]={{0,1},{1,1}}, fin[][2]={{1,1},{1,1}},m[][2]={{0,1},{0,0}};
int mod=666013;
void multiplicare(long long a[][2],long long b[][2])
{
    long long c[2][2];
    c[0][0] = (a[0][0]*b[0][0]+ a[0][1]*b[1][0])%mod;
    c[0][1] = (a[0][0]*b[0][1]+ a[0][1]*b[1][1])%mod;
    c[1][0] = (a[1][0]*b[0][0]+ a[1][1]*b[0][1])%mod;
    c[1][1] = (a[1][0]*b[0][1]+ a[1][1]*b[1][1])%mod;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            a[i][j]=c[i][j];
}

int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    long long n;
    in >> n;
    n--;
    while(n>0)
    {
        if(n%2!=0)
        {
            n--;
            multiplicare(fin,init);
        }
        n=n/2;
        multiplicare(init,init);
    }
    multiplicare(init,m);
    out << init[2][2];
    return 0;
}