#include <bits/stdc++.h>
#define mod 666013

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
int n;
int Z[2][2] = {{0, 1},
               {1, 1}};
int x[2][2] = {{1, 0},
               {0, 1}};

static inline void inmul(int a[2][2], int b[2][2]) {
    int aux[2][2] = {{0, 0},
                     {0, 0}};

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

    a[0][0] = aux[0][0];
    a[1][0] = aux[1][0];
    a[0][1] = aux[0][1];
    a[1][1] = aux[1][1];
}

static inline void put(int n, int x[2][2], int Z[2][2]) {
    while(n) {
        if(n % 2 == 1) inmul(x, Z);
        inmul(Z, Z);
        n /= 2;
    }
}

int main() {
    fin >> n;
    put(n, x, Z);
    fout << x[0][1];

    return 0;
}