#include <bits/stdc++.h>



using namespace std;



ifstream fin("kfib.in");

ofstream fout("kfib.out");



const int MOD=666013;



struct Mat{

    int mat[2][2];

};



Mat inmultire(Mat a,Mat b)

{

    Mat rez;

    rez.mat[0][0] = (1LL * a.mat[0][0] * b.mat[0][0] + 1LL * a.mat[0][1] * b.mat[1][0]) % MOD;

    rez.mat[0][1] = (1LL * a.mat[0][0] * b.mat[0][1] + 1LL * a.mat[0][1] * b.mat[1][1]) % MOD;

    rez.mat[1][0] = (1LL * a.mat[1][0] * b.mat[0][0] + 1LL * a.mat[1][1] * b.mat[1][0]) % MOD;

    rez.mat[1][1] = (1LL * a.mat[1][0] * b.mat[0][1] + 1LL * a.mat[1][1] * b.mat[1][1]) % MOD;

    return rez;

}



Mat putere(Mat a,int e)

{

    Mat rez;

    rez.mat[0][0]=1;

    rez.mat[0][1]=0;

    rez.mat[1][1]=1;

    rez.mat[1][0]=0;





    while(e)

    {

        if(e%2==1)

            rez=inmultire(rez,a);

        a=inmultire(a,a);

        e=e/2;

    }



    return rez;

}



int fibo(int k)

{

    Mat x;

    x.mat[0][0]=0;

    x.mat[0][1]=1;

    x.mat[1][0]=1;

    x.mat[1][1]=1;



    Mat M=putere(x,k-1);



    return M.mat[1][1];

}



int main()

{

    int k;

    fin>>k;

    fout<<fibo(k);

    return 0;

}