#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MOD=666013;
int mat[3][3];
int sol[3][3];
void mult(int a[3][3],int b[3][3])
{
    int c[3][3];
    memset(c,0,sizeof(c));
    for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++)
    for(int k=1;k<=2;k++)
        c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;
    memcpy(a,c,sizeof(c));
}
void put(int put,int rez[3][3])///pun in a valoarea mat^k
{
    rez[1][1]=rez[2][2]=1;///I2
    int val[3][3];
    memcpy(val,mat,sizeof(mat));
    while(put)
    {
        if(put%2==1)
        {
            mult(rez,val);
            put--;
        }
        else
        {
            mult(val,val);
            put/=2;
        }
    }
}
int main()
{
    int k;
    fin>>k;
    mat[1][2]=mat[2][1]=mat[2][2]=1;
    put(k-1,sol);
    fout<<sol[2][2];
    return 0;
}