#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int MOD=666013;
int z[2][2]= {{0,1},{1,1}};
inline void prod(int a[2][2],int b[2][2],int c[2][2])
{
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                a[i][j]=(a[i][j]+b[i][k]*c[k][j])%MOD;

}
int main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int n;
    cin>>n;
    int sol[2][2]= {{1,0},{0,1}};
    int aux[2][2];
    n--;
    for( ; n; n>>=1)
    {
        if(n&1)
        {
            memset(aux,0,sizeof(aux));
            prod(aux,sol,z);
            memcpy(sol,aux,sizeof(aux));
        }
        memset(aux,0,sizeof(aux));
        prod(aux,z,z);
        memcpy(z,aux,sizeof(aux));
    }
    cout<<sol[1][1]<<'\n';
    return 0;
}