#include <fstream>
#include <cstring>

#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int A[2][2],I[2][2];
void inmultire(int A[][2],int B[][2])
{
    int C[2][2],i,j,k;
    for(i=0;i<2;i++)
    {
        for(j=0;j<2;j++)
        {
            C[i][j] = 0;
            for(k=0;k<2;k++)
            {
                C[i][j] = (C[i][j] + 1ll*A[i][k]*B[k][j])%MOD;
            }
        }
    }
    memcpy(A,C,sizeof C);
}
int main()
{
    int k;
    fin>>k;
    A[0][0] = 0;
    A[0][1] = A[1][0] = A[1][1] = 1;
    I[0][0] = I[1][1] = 1;
    k--;
    for(int i=0;(1<<i)<=k;i++)
    {
        if((1<<i) & k)
        {
            inmultire(I,A);
        }
        inmultire(A,A);
    }
    fout<<(I[0][0]+I[1][0])%MOD;
    return 0;
}