#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 666013;
int n, F[2][2];

void lgput(int a[2][2], int put){
    int ans[2][2];
    ans[0][0] = 1; ans[0][1] = 0;
    ans[1][0] = 0; ans[1][1] = 1;
    while (put){
        if (put & 1){
            ll c[2][2];
            c[0][0] = c[1][0] = c[1][1] = c[0][1] = 0;
            for (int i=0; i<2; i++)
                for (int j=0; j<2; j++)
                    for (int w=0; w<2; w++) c[i][j] += 1LL * ans[i][w] * a[w][j];
            ans[0][0] = c[0][0]%mod; ans[0][1] = c[0][1]%mod;
            ans[1][0] = c[1][0]%mod; ans[1][1] = c[1][1]%mod;
        }
        ll c[2][2];
        c[0][0] = c[1][0] = c[1][1] = c[0][1] = 0;
        for (int i=0; i<2; i++)
            for (int j=0; j<2; j++)
                for (int w=0; w<2; w++) c[i][j] += 1LL * a[i][w] * a[w][j];
        a[0][0] = c[0][0]%mod; a[0][1] = c[0][1]%mod;
        a[1][0] = c[1][0]%mod; a[1][1] = c[1][1]%mod;
        put >>= 1;
    }
    a[0][0] = ans[0][0]; a[0][1] = ans[0][1];
    a[1][0] = ans[1][0]; a[1][1] = ans[1][1];
}

int main(){
    ifstream cin ("kfib.in");
    ofstream cout ("kfib.out");
    cin >> n;
    F[0][1] = F[1][0] = F[1][1] = 1;
    if (n < 2) return cout << n, 0;
    lgput(F, n-1);
    cout << F[1][1];
    return 0;
}