#include <iostream>
#include <fstream>
#define mod 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long sol[5][5],mat[5][5];
int i,j,n,m,k,t,p,r,c;
void exponentiere(long long A[5][5],long long B[5][5])
{
    long long C[4][4],i,j,k;
    for(i=1;i<=2;i++)
    for(j=1;j<=2;j++){
        C[i][j]=0;
    for(k=1;k<=2;k++)
    C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;
    }
    for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
    A[i][j]=C[i][j];
}
int main()
{
    f>>k;
    sol[1][1]=0;
    sol[1][2]=1;
    mat[1][1]=0;
    mat[2][1]=1;
    mat[1][2]=1;
    mat[2][2]=1;
    k=k-1;
    while(k!=0)
    {
        if(k%2!=0)
        {
            exponentiere(sol,mat);
        }
        exponentiere(mat,mat);
        k=k/2;
    }
    g<<sol[1][2];
    return 0;
}