#include <iostream>
#include <cstring>
#include <fstream>
#define mod 666013

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
void mult(int A[][3], int C[][3], int AUX[][3])
{
    for(int i = 1; i <= 2; i++)
    {
        for(int j = 1; j <= 2; j++)
        {
            for(int k = 1; k <= 2; k++)
            {
                AUX[i][j] = (AUX[i][j] + (long long) A[i][k] * C[k][j]) % mod;
            }
        }
    }
}

void log_pow(int A[][3], int p)
{
    int AUX[3][3], C[3][3];
    C[1][1] = 0; C[1][2] = C[2][1] = C[2][2] = 1;
    memcpy(A, C, sizeof(C));
    A[1][1] = 1;

    while(p)
    {
        if(p % 2 == 1)
        {
            memset(AUX, 0, sizeof(AUX));
            mult(A, C, AUX);
            memcpy(A, AUX, sizeof(AUX));
        }

        p /= 2;
        memset(AUX, 0, sizeof(AUX));
        mult(C, C, AUX);
        memcpy(C, AUX, sizeof(AUX));
    }
}

int main()
{
    int n, A[3][3], M[3][2], C[3][3];
    fin >> n;
    if(n == 0)
    {
        fout << 0;
        return 0;
    }
    if(n == 1)
    {
        fout << 1;
        return 1;
    }

    log_pow(A, n - 2);

    fout << A[2][2];

    return 0;
}