#include <fstream>

using namespace std;

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

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

void inmultire(long int a[2][2], long int b[2][2])
{
    c[0][0]=(a[0][0] * b[0][0])%666013 + (a[0][1] * b[1][0])%666013;
    c[0][1]=(a[0][0] * b[0][1])%666013 + (a[0][1] * b[1][1])%666013;
    c[1][0]=(a[1][0] * b[0][0])%666013 + (a[1][1] * b[0][1])%666013;
    c[1][1]=(a[1][0] * b[0][1])%666013 + (a[1][1] * b[1][1])%666013;
}
int ridicare(int y)
{
    bool w=0;
    if(y == 1)
        return 0;
    for(int i = y; i > 0; i = i/2)
    {
       if(i % 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 0;
}

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