#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;
}