#include <iostream>
#include <fstream>

using namespace std;

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

const int mod = 666013;

int k;
int start[5][5], aux[5][5];

void Read(){
    fin >> k;
}

void Initialize(){
    start[1][2] = 1;
    aux[1][2] = 1;
    aux[2][1] = 1;
    aux[2][2] = 1;
}

void MultiplyMatrices(int a[5][5], int b[5][5]){
    int c[5][5];
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++)
            c[i][j] = 0;
    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] + 1LL * a[i][k] * b[k][j]) % mod;
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++)
            a[i][j] = c[i][j];
}

void LogPower(int p){
    while (p){
        if (p % 2)
            MultiplyMatrices(start, aux);
        MultiplyMatrices(aux, aux);
        p /= 2;
    }
}

void Print(){
    if (k == 0)
        fout << 0 << '\n';
    else
        fout << start[1][2] << '\n';
}

int main(){
    Read();
    Initialize();
    LogPower(k - 1);
    Print();
    return 0;
}