#include <bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int n;
int MAT[3][3], SOL[3][3];

void mult(int A[][3],int B[][3],int C[][3])
{
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            for(int k=0;k<2;++k)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % mod;
}

void lg_power(int P, int M[][3])
{
    int C[3][3],AUX[3][3];

    memcpy(C,MAT,sizeof(MAT));
    M[0][0] = M[1][1] = 1;
    for(int i=0;(1<<i)<=P;++i)
        {
            if(P & (1<<i))
            {
                memset(AUX,0,sizeof(AUX));
                mult(M,C,AUX);
                memcpy(M,AUX,sizeof(AUX));
            }
            memset(AUX,0,sizeof(AUX));
            mult(C,C,AUX);
            memcpy(C,AUX,sizeof(C));
        }
}

int main()
{
    f>>n;
    MAT[0][0] = 0; MAT[0][1] = MAT[1][0] = MAT[1][1] = 1;
    lg_power(n-1,SOL);
    g<<SOL[1][1];
    return 0;
}