#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;i++)
    for(int k=0;k<2;i++)
        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;
}