#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");

#define pb push_back
const int NMax = 1e5 + 5;
const int mod = 666013;

int K;

void pw(int[2][2],int);

void prod(int[2][2],int[2][2]);

int main() {
    in>>K;

    int st[2][2] = {0,1,1,1},
        dr[2][2] = {0,0,1,0};

    pw(st,K);
    prod(st,dr);

    out<<st[0][0]<<'\n';

    in.close();
    out.close();
    return 0;
}

void pw(int base[2][2],int exp) {
    int ans[2][2] = {1,0,0,1};

    while (exp) {
        if (exp & 1) {
            prod(ans,base);
        }
        prod(base,base);
        exp >>= 1;
    }

    for (int i=0;i < 2;++i) {
        for (int j=0;j < 2;++j) {
            base[i][j] = ans[i][j];
        }
    }
}

void prod(int a[2][2],int b[2][2]) {
    int c[2][2] = {};

    for (int i=0;i < 2;++i) {
        for (int j=0;j < 2;++j) {
            for (int k=0;k < 2;++k) {
                c[i][j] += (1LL * a[i][k] * b[k][j]) % mod;
            }
        }
    }

    for (int i=0;i < 2;++i) {
        for (int j=0;j < 2;++j) {
            a[i][j] = c[i][j] % mod;
        }
    }
}