#include <fstream>
#include <iostream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long int n[] = { 0,1 }, mat[][2] = { {0,1},{1,1} }, p, a,i,j,k,mat1[2][2];
void lgput();
int main()
{
    fin >> p;
    p--;
        a = 1;
        lgput();
        fout << mat[1][1];
    return 0;
}

void lgput()
{
    int mat2[2][2], a1 = a;
    for (i = 0; i <= 1; i++)
        for (j = 0; j <= 1; j++)
        {
            mat2[i][j] = mat[i][j];
        }
    if (2*a <= p)
    {
        for(i=0;i<=1;i++)
            for (j = 0; j <= 1; j++)
                for (k = 0; k <= 1; k++)
                {
                    mat1[i][j] = (mat1[i][j] + (mat[i][k] * mat[k][j])% 666013)% 666013;
                }
        for (i = 0; i <= 1; i++)
            for (j = 0; j <= 1; j++)
            {
                mat[i][j] = mat1[i][j];
                mat1[i][j] = 0;
            }
        a = a * 2;
        lgput();
        if (a + a1 <= p) {
            for (i = 0; i <= 1; i++)
                for (j = 0; j <= 1; j++)
                    for (k = 0; k <= 1; k++)
                    {
                        mat1[i][j] = (mat1[i][j] + (mat[i][k] * mat2[k][j])% 666013)% 666013;
                    }
            for (i = 0; i <= 1; i++)
                for (j = 0; j <= 1; j++)
                {
                    mat[i][j] = mat1[i][j];
                    mat1[i][j] = 0;
                }
            a = a + a1;
        }
    }
}