#include <fstream>
#include <cstring>
#define mod 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long int n,mat[3][3],rez[3][3];
void inmult(long long int A[][3],long long int B[0][3],long long int C[][3])
{
    for (int i=0;i<=1;i++)
    {
        for (int j=0;j<=1;j++)
        {
            for (int k=0;k<=1;k++)
            {
                C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;
            }
        }
    }
}
void ridicare(int p){
    long long int AUX[3][3],A[3][3];
    memcpy(A,mat,sizeof A);
    rez[1][1]=rez[0][0]=1;
    for (long long int i=0;(1<<i)<=p;i++)
    {
        if (p &(1<<i))
        {
            memset(AUX,0,sizeof AUX);
            inmult(rez,A,AUX);
            memcpy(rez,AUX,sizeof AUX);
        }
            memset(AUX,0,sizeof AUX);
            inmult(A,A,AUX);
            memcpy(A,AUX,sizeof AUX);
    }
}
int main()
{
    fin>>n;
    mat[0][0]=0;
    mat[0][1]=mat[1][0]=mat[1][1]=1;
    ridicare(n-1);
    fout<<rez[1][1];
    return 0;
}