#include<iostream>
std::ifstream fin("kfib.in");
std::ofstream fout("kfib.out");
#define mod 666013
unsigned long long mat[2][2]={1, 1, 1, 0};
unsigned long long prod[2][2]={1, 0, 0, 1};
void multiplyMat(unsigned long long a[2][2], unsigned long long b[2][2])
{
    unsigned long long aux[2][2];
    for(int index=0; index<2; ++index)
        for(int next=0; next<2; ++next)
        {
            unsigned long long s=0;
            for(int k=0; k<2; ++k)
                s=(s+(a[index][k]*b[k][next])%mod)%mod;
            aux[index][next]=s;
        }
    for(int index=0; index<2; ++index)
        for(int next=0; next<2; ++next)
            a[index][next]=aux[index][next];
}
void put(unsigned long long power)
{
    while(power)
    {
        if(power%2)
            multiplyMat(prod, mat);
        multiplyMat(mat, mat);
        power/=2;
    }
}
int main()
{
    unsigned long long num;
    fin>>num;
    put(num-2);
    fout<<(prod[0][0]+prod[0][1])%mod;
    return 0;
}
//660634