#include <bits/stdc++.h>

using namespace std;

const int MOD=666013;
const int N=2;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void multiply(long long a[N][N], long long b[N][N]) {

    //calculeaza a * b. rezultatul ==> a
    long long rez[N][N];
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            rez[i][j] = 0;
            for(int k = 0; k < N; k++)
                rez[i][j]=(rez[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
        }
    }

    ///a <-- rez
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            a[i][j] = rez[i][j];
}

void power(long long a[N][N], long long n) {
    ///a^n % MOD
    long long rez[N][N];
    ///initial rez = In
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(i == j)
                rez[i][j] = 1;
            else
                rez[i][j] = 0;

    while(n > 0) {
        if(n % 2 == 1)
            multiply(rez, a);

        multiply(a, a);
        n = n / 2;
    } ///a <-- rez

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            a[i][j] = rez[i][j];
}

int main() {
    long long mt[N][N] = {{0,1},{1,1}};
    long long n;
    fin>>n;
    n=n-1;

    ///calculam mat^n
    power(mt, n);

    ///fib(0)=1, fib(1)=1
    ///(fib(0), fib(1)) * mat^n = (fib(n), fib(n+1))
    long long fibn = (mt[0][0] * 1 + mt[0][1] * 1) % MOD;
    fout << fibn;
    return 0;
}