#include <bits/stdc++.h>
#define mod 666013

using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

void usain_bolt()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
}

long long sol[3][3], aux[3][3], add[3][3];

void mult(long long A[3][3], long long B[3][3], long long C[3][3])
{
    for(int i = 1; i <= 2; ++i) {
        for(int j = 1; j <= 2; ++j) {
            for(int k = 1; k <= 2; ++k) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j] % mod) % mod;
            }
        }
    }
}

void exp(int n)
{
    add[1][1] = 0, add[1][2] = 1;
    add[2][1] = 1, add[2][2] = 1;
    sol[1][1] = 1, sol[2][2] = 1;
    while(n > 0) {
        if(n & 1) {
            memset(aux, 0, sizeof(aux));
            mult(sol, add, aux);
            memcpy(sol, aux, sizeof(aux));

        }
        memset(aux, 0, sizeof(aux));
        mult(add, add, aux);
        memcpy(add, aux, sizeof(aux));
        n >>= 1;
    }
}

int main()
{
    usain_bolt();

    int n;

    fin >> n;
    exp(n - 1);
    fout << (sol[2][2] + mod) % mod;
    return 0;
}