#include <fstream>
#include <iostream>
#define mod 666013
using namespace std;
long long def[3][3],a[3][3],b[3][3],n;
void doit(long long v[][3],int exp)
{
    if (exp==1)
        return;
    if (exp%2==0)
    {
        doit(v,exp/2);
        for (int i=1; i<=2; i++)
            for (int j=1; j<=2; j++)
                b[i][j]=0;
        for (int i=1; i<=2; i++)
            for (int j=1; j<=2; j++)
            {
                for (int l=1; l<=2; l++)
                    b[i][j]=b[i][j]+v[i][l]*v[l][j];
            }
        for (int i=1; i<=2; i++)
            for (int j=1; j<=2; j++)
                v[i][j]=b[i][j]%mod;
        return;
    }
    else
    {
        doit(v,exp-1);
        for (int i=1; i<=2; i++)
            for (int j=1; j<=2; j++)
                b[i][j]=0;
        for (int i=1; i<=2; i++)
            for (int j=1; j<=2; j++)
            {
                for (int l=1; l<=2; l++)
                    b[i][j]=b[i][j]+v[i][l]*def[l][j];
            }
        for (int i=1; i<=2; i++)
            for (int j=1; j<=2; j++)
                v[i][j]=b[i][j]%mod;
        return;
    }
}
int main()
{
    ifstream f ("kfib.in");
    ofstream g ("kfib.out");
    f>>n;
    if (n<=2)
    {
        g<<1;
        return 0;
    }
    a[1][2]=a[2][1]=a[2][2]=def[1][2]=def[2][1]=def[2][2]=1;
    doit(a,n);
    g<<a[1][2];
}