#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long c[3][3],n,lg,i,t,k,j,o;
long long  a[3][3]= {{0,0,0},{0,0,1},{0,1,1}};
long long  sol[3][3]= {{0,0,0},{0,1,0},{0,0,1}};
int main()
{
    f>>n;
    if (n<=1)
    {
        g<<"1";
        return 0;
    }
    lg=log2(n);
    for (i=0; i<=lg; i++)
    {
        if ((1<<i)&n)
        {
            memset(c,0,sizeof(c));
            for (t=1; t<=2; t++)
            {
                for (k=1; k<=2; k++)
                {
                    for (o=1; o<=2; o++)
                    {
                        c[t][k]=(c[t][k]+(sol[t][o]*a[o][k])%MOD)%MOD;
                    }
                }
            }
            for (k=1; k<=2; k++)
            {
                for (t=1; t<=2; t++)
                {
                    sol[k][t]=c[k][t];
                }
            }
        }
        memset(c,0,sizeof(c));
        for (k=1;k<=2;k++)
        {
            for (t=1;t<=2;t++)
            {
                for (o=1;o<=2;o++)
                {
                    c[k][t]=(c[k][t]+(1LL*a[k][o]*a[o][t])%MOD)%MOD;
                }
            }
        }
        for (k=1;k<=2;k++)
        {
            for (t=1;t<=2;t++)
            {
                a[k][t]=c[k][t];
            }
        }
    }
    g<<(sol[2][1])%MOD;
    return 0;
}