#include <iostream>
#include <fstream>

using namespace std;

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

int MOD = 666013;
void copiere(long long a[2][2], long long b[2][2]) {
    int i, j;
    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j)
            a[i][j] = b[i][j];
}

void inmultire(long long a[2][2], long long b[2][2], long long c[2][2]){
    long long i, j, k;
    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j){
            c[i][j] = 0;
            for (k = 0; k < 2; ++k) {
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= MOD;
            }
        }
}

long long a[2][2], i3[2][2], t[2][2];

void ridicare(long long a[2][2], long long n){
    int i,j;
    if(n){
        if(n % 2 == 1){
            inmultire(i3, a, t);
            copiere(i3, t);
            ridicare(a, n-1);
        } else {
            inmultire(a, a, t);
            copiere(a, t);
            ridicare(a, n/2);
        }
    }
}

int main()
{
    long long k;
    fin>>k;
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 1;
    a[1][1] = 1;
    i3[0][0] = 1;
    i3[0][1] = 0;
    i3[1][0] = 0;
    i3[1][1] = 1;
    while (k > 0) {
        if (k % 2 == 1) {
            inmultire(i3, a, t);
            copiere(i3, t);
        }
        inmultire(a, a, t);
        copiere(a, t);
        k /= 2;
    }
    fout<<i3[0][1] % MOD;
    return 0;
}