#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD=666013;
const int N=3;
int p=1;
long long k, x[3][3], y[3][3], z[3][3];

void produs (long long a[3][3], long long b[3][3], int n)
{
    long aux[3][3];
    int i, j, k;
    for( i=1; i<=n; i++)
    {
        for(j=1;j<=n;j++)
        {
            aux[i][j]=0;
            for(k=1;k<=n;k++)
            {
                aux[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            a[i][j]=aux[i][j]%MOD;
        }
    }
}

int main()
{
    in>>k;
    x[1][2]=x[2][1]=x[2][2]=1;
    y[1][1]=y[2][2]=1;
    k--;
    while(k>0)
    {
        if(k%2!=0)
        {
            produs (y,x,2);
        }
        k/=2;
        produs (x,x,2);
    }
    out<<y[2][2];
    return 0;
}