#include <fstream>

using namespace std;

#define mod 666013

int getFibonacci(int K);
void matrixMult(long long matrix[][2], long long output[][2]);
void matrixMult(long long matrix1[][2], long long matrix2[][2], long long output[][2]);
void matrixCpy(long long matrix1[][2], long long matrix2[][2]);
void init(long long matrix[][2]);

int main()
{
    int K;
    ifstream f("kfib.in");
    f >> K;
    f.close();

    ofstream g("kfib.out");
    if (K == 1)
        g << 1;
    else
        g << getFibonacci(K - 2);
    g.close();
    return 0;
}

int getFibonacci(int K)
{
    long long Z[][2] = {{0 , 1}, {1, 1}};
    long long result[][2] = {{1, 0}, {0, 1}};
    long long tmp[2][2];
    while (K)
    {
        if (K & 1)
        {
            matrixMult(result, Z, tmp);
            matrixCpy(result, tmp);
        }

        matrixMult(Z, tmp);
        matrixCpy(Z, tmp);
        K >>= 1;
    }

    return (result[0][1] + result[1][1]) % mod;
}

void matrixMult(long long matrix[][2], long long output[][2])
{
    init(output);
    int i, j, k;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            for (k = 0; k < 2; k++)
                output[i][j] += ((matrix[i][k] % mod) * (matrix[k][j] % mod)) % mod;
}

void matrixMult(long long matrix1[][2], long long matrix2[][2], long long output[][2])
{
    init(output);
    int i, j, k;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            for (k = 0; k < 2; k++)
                output[i][j] += ((matrix1[i][k] % mod) * (matrix2[k][j] % mod)) % mod;
}

void matrixCpy(long long matrix1[][2], long long matrix2[][2])
{
    int i, j;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            matrix1[i][j] = matrix2[i][j];
}

void init(long long matrix[][2])
{
    int i, j;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            matrix[i][j] = 0;
}