#include <fstream>
#include <cstring>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const int mod = 666013;
int n, i, j, k;
long long a[2][2], sol[2][2];
long long tmp[2][2];

int main() {
    f >> n;n--;
    sol[0][0] = sol[1][1] = a[1][0]=a[1][1]=a[0][1] = 1;
    while (n) {
        if (n&1) {
            for (i = 0; i < 2; i++)
                for (j = 0; j < 2; j++) {
                    tmp[i][j] = 0;
                    for (k = 0; k < 2; k++)
                        tmp[i][j] = (tmp[i][j] + (sol[i][k] * a[k][j])%mod)%mod;
                }
            memcpy(sol,tmp,sizeof(tmp));
        }
        memset(tmp,0,sizeof(tmp));
        for (i = 0; i < 2; i++)
            for (j = 0; j < 2; j++) {
                tmp[i][j] = 0;
                for (k = 0; k < 2; k++)
                    tmp[i][j] = (tmp[i][j]+(a[i][k] * a[k][j])%mod)%mod;
            }
        memcpy(a,tmp,sizeof(tmp));

        n >>= 1;
    }
    g <<(sol[0][0] + sol[0][1])%mod;
}