#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
///aproapeperm
ifstream fin("kfib.in");
ofstream fout("kfib.out");

int K;
int A[2][2], B[2][2], C[2][2];

void Copiaza(int A[][2], int B[][2])
{
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            A[i][j] = B[i][j];
}
void Inmulteste(int A[][2], int B[][2], int C[][2])
{
    int i, j, k, sum;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
        {
            sum = 0;
            for (k = 0; k < 2; k++)
                sum = (sum + 1LL * A[i][k] * B[k][j]) % MOD;
            C[i][j] = sum;
        }
}
void LogExpo(int A[][2], int Put, int C[][2])
{
    C[0][0] = C[1][1] = 0;
    C[0][1] = C[1][0] = 1;
    while (Put > 0)
    {
        if (Put % 2 == 1)
        {
            Inmulteste(A, C, B);;
            Copiaza(C, B);
        }
        Put /= 2;
        Inmulteste(A, A, B);
        Copiaza(A, B);
    }
}

int main()
{
    fin >> K;
    if (K <= 2)
    {
        fout << K << "\n";
        return 0;
    }
    A[0][0] = 0;
    A[0][1] = A[1][0] = A[1][1] = 1;
    LogExpo(A, K - 2, C);
    A[0][1] = 1;
    A[0][0] = A[1][0] = A[1][1] = 0;
    Inmulteste(A, C, B);
    fout << (B[0][0] + B[0][1]) % MOD << "\n";
    return 0;
}