#include <iostream>
#include <fstream>

using namespace std;

const int mod = 666013;

int z[3][3], baza[3][3], c[3][3];

void prod(int a[3][3], int b[3][3]){
    for(int i = 1; i <= 2; ++i){
        for(int j = 1; j <= 2; ++j){
            c[i][j] = 0;
            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];
    }
}

int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    int n;
    fin >> n;
    baza[1][2] = baza[2][1] = baza[2][2] = z[1][2] = z[2][1] = z[2][2] = 1;
    n -= 2;
    while(n){
        if(n % 2 == 1){
            prod(z, baza);
            prod(baza, baza);
            n /= 2;
        }
        else{
            prod(baza, baza);
            n /= 2;
        }
    }
    int rez = z[2][2] % mod;
    fout << rez;
    return 0;
}