#include <iostream>

using namespace std;

const int MOD = 666013;

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

void matrix_power(int m[2][2], int exp, int rez[2][2])
{
    if(exp == 0)
    {
        rez[0][0] = 1, rez[0][1] = 0, rez[1][0] = 0, rez[1][1] = 1;
        return;
    }

    int aux[2][2];
    matrix_power(m, exp / 2, aux);
    multiply(aux, aux, rez);
    if(exp % 2 != 0)
    {
        aux[0][0] = rez[0][0], aux[0][1] = rez[0][1], aux[1][0] = rez[1][0], aux[1][1] = rez[1][1];
        multiply(aux, m, rez);
    }
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int k;
    cin >> k;

    int mat[2][2] = {0}, rez[2][2] = {0};
    mat[0][1] = mat[1][0] = mat[1][1] = 1;

    if(k < 2)
    {
        cout << 1;
        return 0;
    }

    matrix_power(mat, k - 2, rez);

    cout << (rez[0][1] + rez[1][1]) % MOD;
    return 0;
}