#include <fstream>

using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

long int x[2][2], rez[2][2], p[2][2], er;
long long c[2][2];

void inmultire(long int a[2][2], long int b[2][2])
{
    long long jk2, jk;

    jk = a[0][0]%666013;
    jk*= b[0][0]%666013;
    jk%=666013;

    jk2 = a[0][1]%666013;
    jk2*= b[1][0]%666013;
    jk2%=666013;

    c[0][0]=(jk+ jk2)%666013;

    // 2
    jk = a[0][0]%666013;
    jk*= b[0][1]%666013;
    jk%=666013;

    jk2 = a[0][1]%666013;
    jk2*= b[1][1]%666013;
    jk2%=666013;

    c[0][1]=(jk + jk2)%666013;

    //3
    jk = a[1][0]%666013;
    jk*= b[0][0]%666013;
    jk%=666013;

    jk2 = a[1][1]%666013;
    jk2*= b[0][1]%666013;
    jk2%=666013;

    c[1][0]=(jk + jk2)%666013;

    //4
    jk = a[1][0]%666013;
    jk*= b[0][1]%666013;
    jk%=666013;

    jk2 = a[1][1]%666013;
    jk2*= b[1][1]%666013;
    jk2%=666013;

    c[1][1]=(jk + jk2)%666013;
}
void ridicare(long int y)
{
    bool w=0;
    if(y == 1)
        return ;
    for(er = y; er > 0; er = er/2)
    {
        if(er % 2 == 1)
        {
            if (w == 1)inmultire(rez, p);
            w = 1;
            for (int i = 0; i<2; i++)
                for (int j = 0; j<2; j++)rez[i][j]=c[i][j]%666013;
        }
        inmultire(p, p);
        for (int i = 0; i<2; i++)
            for (int j = 0; j<2; j++)p[i][j]=c[i][j]%666013;
    }
    return;
}

int main()
{
    long int k;

    fin >> k;

    p[0][1]=1;
    p[1][0]=1;
    p[1][1]=1;

    c[0][1]=1;
    c[1][0]=1;
    c[1][1]=1;
    ridicare(k+1);

    fout << rez[0][0];
    return 0;
}