#include <iostream>
#include <fstream>

using namespace std;

const int mod=666013;
long long a[2][2]={{0,1},{1,1}}, b[2][2]={{1,0},{0,1}};

void hatvany(int n)
{
    if(n!=1)
        if(n%2==0){
            long long aux[2][2], aux2[2][2];
            aux[0][0]=aux2[0][0]=a[0][0];
            aux[0][1]=aux2[0][1]=a[0][1];
            aux[1][0]=aux2[1][0]=a[1][0];
            aux[1][1]=aux2[1][1]=a[1][1];

            a[0][0]=(aux[0][0]*aux2[0][0]+aux[0][1]*aux2[1][0])%mod;
            a[0][1]=(aux[0][0]*aux2[0][1]+aux[0][1]*aux2[1][1])%mod;
            a[1][0]=(aux[1][0]*aux2[0][0]+aux[1][1]*aux2[1][0])%mod;
            a[1][1]=(aux[1][0]*aux2[0][1]+aux[1][1]*aux2[1][1])%mod;
            hatvany(n/2);
        } else{
            long long aux[2][2], aux2[2][2];
            aux[0][0]=b[0][0];
            aux[0][1]=b[0][1];
            aux[1][0]=b[1][0];
            aux[1][1]=b[1][1];

            b[0][0]=(a[0][0]*aux[0][0]+a[0][1]*aux[1][0])%mod;
            b[0][1]=(a[0][0]*aux[0][1]+a[0][1]*aux[1][1])%mod;
            b[1][0]=(a[1][0]*aux[0][0]+a[1][1]*aux[1][0])%mod;
            b[1][1]=(a[1][0]*aux[0][1]+a[1][1]*aux[1][1])%mod;

            aux[0][0]=aux2[0][0]=a[0][0];
            aux[0][1]=aux2[0][1]=a[0][1];
            aux[1][0]=aux2[1][0]=a[1][0];
            aux[1][1]=aux2[1][1]=a[1][1];

            a[0][0]=(aux[0][0]*aux2[0][0]+aux[0][1]*aux2[1][0])%mod;
            a[0][1]=(aux[0][0]*aux2[0][1]+aux[0][1]*aux2[1][1])%mod;
            a[1][0]=(aux[1][0]*aux2[0][0]+aux[1][1]*aux2[1][0])%mod;
            a[1][1]=(aux[1][0]*aux2[0][1]+aux[1][1]*aux2[1][1])%mod;
            hatvany((n-1)/2);
        }
}
int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    int k, c;
    f>>k;
    hatvany(k-1);
    g<<(a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod;
    ;return 0;
}