#include <bits/stdc++.h>

#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

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

int main()
{
    fin >> n;
    mat[0][0] = mat[1][1] = 1;
    c[0][1] = c[1][0] = c[1][1] = 1;
    while(n){
        if(n % 2 == 1)
            inmultire(mat, c);
        inmultire(c, c);
        n /= 2;
    }
    fout << mat[0][1];
    /*
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            fout << mat[i][j] << " ";
        fout << '\n';
    */
}