#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int mod=666013;
int I[3][3]={{0,1,0},{0,0,1},{0,1,1}},F2[3]={0,1,1};
void x(int v1[][3],int v2[][3])
{
    int res[3][3]={0};
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                res[i][j]=(res[i][j]+1ll*v1[i][k]*v2[k][j]%mod)%mod;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            v1[i][j]=res[i][j];
}
void power(int putere)
{
    int res[3][3]={{1,0,0},{0,1,0},{0,0,1}};
    while(putere)
    {
        if(putere%2)
            x(res,I);
        x(I,I);
        putere/=2;
    }
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            I[i][j]=res[i][j];
}
int main()
{
    int n;
    fin>>n;
    if(n<3)
    {
        fout<<F2[n];
        return 0;
    }
    power(n-2);
    fout<<(I[2][1]*F2[1]%mod+I[2][2]*F2[2]%mod)%mod;



    return 0;
}