#include <bits/stdc++.h>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const int Mod=666013;
int suma(int x,int y)
{
    x=(x+y)%Mod;
    return x;
}
int prod(int x,int y)
{
    x=1LL*x*y%Mod;
    return x;
}
struct matrix
{
    int M[2][2];
    matrix()
    {
        for(int i=0; i<2; i++)for(int j=0; j<2; j++)M[i][j]=0;
    }
    matrix(int a,int b,int c,int d)
    {
        M[0][0]=a;
        M[0][1]=b;
        M[1][0]=c;
        M[1][1]=d;
    }
};
matrix operator*(matrix a,matrix b)
{
    matrix p;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                p.M[i][j]=suma(p.M[i][j],prod(a.M[i][k],b.M[k][j]));
    return p;
}
matrix operator^(matrix B,int e)
{
    if(e==0)return matrix(1,0,0,1);
    matrix R=B^(e/2);
    R=R*R;
    if(e%2)R=R*B;
    return R;
}
int main()
{
    int k;
    f>>k;
    g<<(matrix(1,1,1,0)^k).M[0][1];
    return 0;
}