#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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


const int MOD=666013;

struct Mat
{
    long long a11,a12,a22;
};

Mat A = {1, 1, 0};
Mat P= {1,0,1};


void mul(Mat &A, Mat &B)
{
    long long x=A.a11* B.a11+A.a12*B.a12;
    long long y=A.a11* B.a12+A.a12*B.a22;
    long long z=A.a12* B.a12+A.a22*B.a22;
    A.a11=x%MOD;
    A.a12=y%MOD;
    A.a22=z%MOD;
}

void putere(int n)
{
    while(n>0)
        if(n%2==0)
        {
            mul(A, A);
            n/=2;
        }

        else
        {
            mul(P,A);
            n--;
        }
}




int main()
{
    int k;
    f>>k;
    if(k>0)
    {
        putere(k-1);
        g<<P.a11;
    }
    else
    {
        g<<'0';
    }
    return 0;
}