#include <bits/stdc++.h>
#define val 666013
#define LL long long
using namespace std;

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

LL z[2][2] = {0 , 1, 1, 1};

void inmultire1(LL a[][2], LL b[][2]) {
    int cpy[1][2];
    
    cpy[0][0] = a[0][0] * b[0][0] % val + a[0][1] * b[1][0] % val;
    cpy[0][1] = a[0][0] * b[0][1] % val + a[0][1] * b[1][1] % val;
    
    a[0][0] = cpy[0][0];
    a[0][1] = cpy[0][1];
}

void inmultire2 (LL a[][2], LL b[][2]) {
    int cpy[2][2];
    
    cpy[0][0] = a[0][0] * b[0][0] % val + a[0][1] * b[1][0] % val;
    cpy[0][1] = a[0][0] * b[0][1] % val + a[0][1] * b[1][1] % val;
    cpy[1][0] = a[1][0] * b[0][0] % val + a[1][1] * b[1][0] % val;
    cpy[1][1] = a[1][0] * b[0][1] % val + a[1][1] * b[1][1] % val;
    
    a[0][0] = cpy[0][0];
    a[0][1] = cpy[0][1];
    a[1][0] = cpy[1][0];
    a[1][1] = cpy[1][1];
}

void fibonacciCrazy(int n, LL m[][2]) {
    if (n >= 1) {
        if (n % 2) 
            inmultire1(m, z);
        
        inmultire2(z, z);
        fibonacciCrazy(n / 2, m);
    }
}

int main(void) {
    LL n, m[1][2] = {0, 1};
    fin >> n;
    
    fibonacciCrazy(n, m);
    
    fout << m[0][0];
    
    return 0;
}