#include <bits/stdc++.h>

using namespace std;

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

const int MOD=666013;

inline int prod(int x, int y)
{
    x=(1LL*x*y)%MOD;
    return x;
}

inline int suma(int x, int y)
{
    x=(x+y)%MOD;
    return x;
}

struct matrix
{
    int a[2][2];
    matrix()
    {
        for(int i=0; i<2; i++)
            for(int j=0; j<2; j++)
                a[i][j]=0;
    }
    matrix(int x, int y, int z, int t)
    {
        a[0][0]=x;
        a[0][1]=y;
        a[1][0]=z;
        a[1][1]=t;
    }
};

matrix operator * (matrix A, matrix B)
{
    matrix C;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                C.a[i][j]=suma(C.a[i][j],prod(A.a[i][k],B.a[k][j]));
    return C;
}

matrix operator ^ (matrix A, int e)
{
    if(e==0)
        return matrix(1,0,0,1);
    matrix R=A^(e/2);
    R=R*R;
    if(e&1)
        R=A*R;
    return R;
}

int k;


int main()
{
    inf >>k;
    outf<<(matrix(0,1,1,1)^k).a[0][1];
    return 0;
}