#include <fstream>
#include <cstring>

using namespace std;

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

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

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