#include <bits/stdc++.h>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const int64_t MOD = 666013;
int64_t n,f0,f1,z;
int64_t F[1000001];
struct matrix
{
    int64_t a[2][2];
    matrix()
    {
        a[0][0]=a[1][0]=a[0][1]=a[1][1]=0;
    }
    matrix(int64_t a00,int64_t a01,int64_t a10,int64_t a11)
    {
        a[0][0]=a00;
        a[0][1]=a01;
        a[1][0]=a10;
        a[1][1]=a11;
    }

};
matrix operator*(matrix A,matrix B)
{
    matrix R;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
               R.a[i][j]=(R.a[i][j]+A.a[i][k]*B.a[k][j]%MOD)%MOD;
    return R;
}
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%2)R=A*R;
    return R;
}

int main()
{
    f>>n;
    g<<(matrix(1,1,1,0)^n).a[0][1];
    return 0;
}