#include <fstream>
#define DIV 666013
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int main()
{
    long long p,n[2][2],a[2][2],aux[2][2];
    a[0][0]=1;a[0][1]=0;a[1][0]=0;a[1][1]=1;
    n[0][0]=0;n[0][1]=1;n[1][0]=1;n[1][1]=1;
    f>>p;
    for(;p>1;p>>=1)
    {
        if(p%2==1)
        {
            aux[0][0]=(a[0][0]*n[0][0]+a[0][1]*n[1][0])%DIV;
            aux[0][1]=(a[0][0]*n[0][1]+a[0][1]*n[1][1])%DIV;
            aux[1][0]=(a[1][0]*n[0][0]+a[1][1]*n[1][0])%DIV;
            aux[1][1]=(a[1][0]*n[0][1]+a[1][1]*n[1][1])%DIV;
            a[0][0]=aux[0][0];a[0][1]=aux[0][1];a[1][0]=aux[1][0];a[1][1]=aux[1][1];
        }
        aux[0][0]=(n[0][0]*n[0][0]+n[0][1]*n[1][0])%DIV;
        aux[0][1]=(n[0][0]*n[0][1]+n[0][1]*n[1][1])%DIV;
        aux[1][0]=(n[1][0]*n[0][0]+n[1][1]*n[1][0])%DIV;
        aux[1][1]=(n[1][0]*n[0][1]+n[1][1]*n[1][1])%DIV;
        n[0][0]=aux[0][0];n[0][1]=aux[0][1];n[1][0]=aux[1][0];n[1][1]=aux[1][1];
    }
    aux[0][0]=(a[0][0]*n[0][0]+a[0][1]*n[1][0])%DIV;
    aux[0][1]=(a[0][0]*n[0][1]+a[0][1]*n[1][1])%DIV;
    aux[1][0]=(a[1][0]*n[0][0]+a[1][1]*n[1][0])%DIV;
    aux[1][1]=(a[1][0]*n[0][1]+a[1][1]*n[1][1])%DIV;
    a[0][0]=aux[0][0];a[0][1]=aux[0][1];a[1][0]=aux[1][0];a[1][1]=aux[1][1];
    g<<a[0][1];
}