#include <fstream>
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long fibonacci_number,mod = 666013;
long long A[3][3];

void inmultire(long long c1[3][3], long long c2[3][3])
{
    long long i,j,aux[3][3];

    aux[0][0] = c1[0][0] * c2[0][0] + c1[0][1] * c2[1][0];
    aux[0][1] = c1[0][0] * c2[0][1] + c1[0][1] * c2[1][1];
    aux[1][0] = c1[1][0] * c2[0][0] + c1[1][1] * c2[1][0];
    aux[1][1] = c1[1][0] * c2[0][1] + c1[1][1] * c2[1][1];

    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++)
        {
            if(aux[i][j] > mod)
                aux[i][j] %= mod;
            c1[i][j] = aux[i][j];
        }
}

void Solve(long long k)
{
    long long w[3][3],i,j;

    if(k>1)
        if(k%2==0)
        {
            inmultire(A,A);
            Solve(k/2);
        }
        else
        {
            for(i=0;i<=1;i++)
                for(j=0;j<=1;j++)
                    w[i][j] = A[i][j];
            inmultire(A,A);
            Solve(k/2);
            inmultire(A,w);
        }
}

int main()
{
    A[0][0] = 0 , A[0][1] = 1;
    A[1][0] = 1 , A[1][1] = 1;

    f>>fibonacci_number;

    Solve(fibonacci_number);

    g<<A[0][1]<<'\n';

    return 0;
}


// 666013