#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int MOD = 666013;

int n, fib[5][5], mat[5][5];

void prod(int row, int col, int mat1[5][5], int mat2[5][5]){
    int answer[5][5];
    for(int i=1; i<=row; i++)
        for(int j=1; j<=col; j++){
            answer[i][j] = 0;
            for(int k=1; k<=col; k++)
                answer[i][j] = (answer[i][j] + (long long)mat1[i][k] * mat2[k][j] % MOD) % MOD;
        }

    for(int i=1; i<=row; i++)
        for(int j=1; j<=col; j++)
            mat1[i][j] = answer[i][j];
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n;

    fib[1][1] = 0; fib[1][2] = 1; /// (1, 1)

    mat[1][1] = 0, mat[1][2] = 1; /// (0, 1)
    mat[2][1] = 1, mat[2][2] = 1; /// (1, 1)

    if(n == 0){
        fout<<0;
        return 0;
    }

    n--;
    while(n != 0){
        if(n & 1)
            prod(1, 2, fib, mat);
        prod(2, 2, mat, mat);
        n >>= 1;
    }

    fout<<fib[1][2];
    return 0;
}
/**
Vreau:
F(i) = F(i-1) + F(i-2)
(F1, F2) -> (F2, F1+F2) = (F2, F3)

(F1, F2) * (0 1) = (X, Y)
           (1 1)

X = F1 * 0 + F2 * 1 = F2
Y = F1 * 1 + F2 * 1 = F1 + F2
**/