#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const long long mod=666013;
int n;
int m[4][4],solv[4][4];
int z[4][4];
void copyx(int m[4][4], int c[4][4])
{
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
            m[i][j]=c[i][j];
    }
}
void const_matrix()
{
    z[1][1]=0;
    z[1][2]=1;
    z[2][1]=1;
    z[2][2]=1;
}
void matrix_multiplication(int m[][4],int b[][4])
{
    int c[4][4]={0};
                 for(int i=1; i<=2; i++)
                     for(int j=1; j<=2; j++)
        {
            for(int nr=1; nr<=2; nr++)
                c[i][j]=(c[i][j]+((1LL*m[i][nr]*b[nr][j])%mod))%mod;
        }
    copyx(m,c);
}
void exp(int expo)
{
    copyx(solv,z);
    expo--;
    while(expo)
    {
        if(expo%2)
        {
            expo--;
            matrix_multiplication(solv,z);
        }
        expo/=2;
        matrix_multiplication(z,z);
    }
}

int main()
{
    fin>>n;
    const_matrix();
    exp(n-1);
    fout<<solv[2][2];
    return 0;
}