#include <iostream>
#include <vector>

#define MOD 666013

using namespace std;

long long v[3];
long long mat[3][3];
long long rez[3];
void rise(long long v[3][3], long long p)
{
    if(p == 0)
    {
        v[1][1] = 1;
        v[1][2] = 0;
        v[2][1] = 0;
        v[2][2] = 1;
        return;
    }

    long long copie[3][3];
    copie[1][1] = v[1][1];
    copie[1][2] = v[1][2];
    copie[2][1] = v[2][1];
    copie[2][2] = v[2][2];

    rise(v, p / 2);

    long long aux[3][3];
    aux[1][1] = (v[1][1] * v[1][1] % MOD + v[1][2] * v[2][1] % MOD) % MOD;
    aux[1][2] = (v[1][1] * v[1][2] % MOD + v[1][2] * v[2][2] % MOD) % MOD;
    aux[2][1] = (v[2][1] * v[1][1] % MOD + v[2][2] * v[2][1] % MOD) % MOD;
    aux[2][2] = (v[2][1] * v[1][2] % MOD + v[2][2] * v[2][2] % MOD) % MOD;
    if(p % 2 == 0)
    {
        v[1][1] = aux[1][1];
        v[1][2] = aux[1][2];
        v[2][1] = aux[2][1];
        v[2][2] = aux[2][2];
        return;
    }

    long long aux2[3][3];
    aux2[1][1] = (aux[1][1] * copie[1][1] % MOD + aux[1][2] * copie[2][1] % MOD) % MOD;
    aux2[1][2] = (aux[1][1] * copie[1][2] % MOD + aux[1][2] * copie[2][2] % MOD) % MOD;
    aux2[2][1] = (aux[2][1] * copie[1][1] % MOD + aux[2][2] * copie[2][1] % MOD ) % MOD;
    aux2[2][2] = (aux[2][1] * copie[1][2] % MOD + aux[2][2] * copie[2][2] % MOD) % MOD;
    v[1][1] = aux2[1][1];
    v[1][2] = aux2[1][2];
    v[2][1] = aux2[2][1];
    v[2][2] = aux2[2][2];
    return;
}

int main()
{
    long long k;
    cin >> k;

    mat[1][1] = 0;
    mat[1][2] = 1;
    mat[2][1] = 1;
    mat[2][2] = 1;

    rise(mat, k - 1);
    rez[1] = 1;
    rez[2] = 1;

    cout << (rez[1] * mat[1][1] + rez[2] * mat[1][2]) % MOD << '\n';
    return 0;
}