#include <bits/stdc++.h>

using namespace std;

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

long long M[2][2],Z[2][2];
const int MOD = 666013;

void multiply(long long A[2][2], long long B[2][2])
{
    long long C[2][2];
    C[0][0] = C[1][0] = C[0][1] = C[1][1] = 0;
    for (int i = 0; i<2; i++)
        for (int j = 0; j<2; j++)
            for (int k = 0; k<2; k++)
                C[i][j] = (C[i][j]+A[i][k]*B[k][j])%MOD;
    for (int i = 0; i<2; i++)
        for (int j = 0; j<2; j++)
            A[i][j] = C[i][j];
}

int main()
{
    M[0][0] = M[1][1] = 1;
    Z[0][1] = Z[1][0] = Z[1][1] = 1;
    long long n;
    in >> n;
    while (n)
    {
        if (n%2)
        {
            multiply(M,Z);
            n--;
        }
        else
        {
            multiply(Z,Z);
            n/=2;
        }
    }
    out << M[1][0];
}