#include <fstream>
#define M 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int unu[3][3],m[3][3],aux[3][3],i,j,n,poz;
int main()
{
    fin>>n;
    //if(n == 0)
        //fout<<0;
    //else if(n == 1 || n == 2)
        //fout<<1;
    //else{
        unu[1][2] = m[1][2] = 1;
        unu[2][2] = m[2][2] = 1;
        unu[2][1] = m[2][1] = 1;
        poz=1;
        while(poz * 2 <= n){
            aux[1][1] = m[1][1] * m[1][1] % M + m[1][2] * m[2][1] % M;
            aux[1][2] = m[1][1] * m[1][2] % M + m[1][2] * m[2][2] % M;
            aux[2][1] = m[2][1] * m[1][1] % M + m[2][2] * m[1][2] % M;
            aux[2][2] = m[2][1] * m[1][2] % M + m[2][2] * m[2][2] % M;
            m[1][1] = aux[1][1] % M;
            m[1][2] = aux[1][2] % M;
            m[2][1] = aux[2][1] % M;
            m[2][2] = aux[2][2] % M;
            poz*=2;
        }
        //fout<<m[1][1]<<" "<<m[1][2]<<'\n';
        //fout<<m[2][1]<<" "<<m[2][2]<<'\n';
        while(poz <= n){
            aux[1][1] = m[1][1] * unu[1][1] % M + m[1][2] * unu[2][1] % M;
            aux[1][2] = m[1][1] * unu[1][2] % M + m[1][2] * unu[2][2] % M;
            aux[2][1] = m[2][1] * unu[1][1] % M + m[2][2] * unu[1][2] % M;
            aux[2][2] = m[2][1] * unu[1][2] % M + m[2][2] * unu[2][2] % M;
            m[1][1] = aux[1][1] % M;
            m[1][2] = aux[1][2] % M;
            m[2][1] = aux[2][1] % M;
            m[2][2] = aux[2][2] % M;
            ++poz;
        }
        //fout<<m[1][1]<<" "<<m[1][2]<<'\n';
        //fout<<m[2][1]<<" "<<m[2][2]<<'\n';
        fout<<m[1][1];
    //}
    return 0;
}