#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 666013;
int f[2][2],p[2][2],a[2][2],aux[2][2];
int n;

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

void mult(int a[2][2], int b[2][2], int c[2][2]){
    /// c = a*b
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            c[i][j] = 0;
            for(int k = 0; k < 2; k++){
                c[i][j] += (a[i][k]*b[k][j])%MOD;
                if(c[i][j] > MOD){
                    c[i][j] -= MOD;
                }
            }
        }
    }
}

signed main()
{
    fin >> n;
    if(n <= 1){
        fout << n;
        return 0;
    }
    f[0][0] = f[1][0] = 1;
    p[0][0] = p[1][1] = 1;
    /// p = [1 0]
    ///     [0 1]
    a[0][0] = a[0][1] = a[1][0] = 1;
    /// a = [1 1]
    ///     [1 0]
    n -= 2;
    while(n){
        if(n&1){
            mult(p, a, aux);
            memcpy(p, aux, sizeof(aux));
        }
        mult(a, a, aux);
        memcpy(a, aux, sizeof(aux));
        n >>= 1;
    }
    mult(p, f, aux);
    memcpy(f, aux, sizeof(aux));
    fout << f[0][0];
    return 0;
}