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

using namespace std;

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

const int MOD = 666013;
int k;
int fib[5][5], mat[5][5], mlg[5][5];

int tmp[5][5];
static inline void prod(int n, int m, int k, int (&mat1)[5][5], int (&mat2)[5][5], int (&mrez)[5][5]){
    ///mat1 = n*m
    ///mat2 = m*k
    ///mrez = n*k

    for(int i=1; i<=n; i++)
        for(int j=1; j<=k; j++){
            tmp[i][j] = 0;
            for(int l=1; l<=m; l++)
                tmp[i][j] = ((long long)tmp[i][j] + (long long)mat1[i][l]*mat2[l][j]%MOD) % MOD;
        }

    for(int i=1; i<=n; i++)
        for(int j=1; j<=k; j++)
            mrez[i][j] = tmp[i][j];
}

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

    fin>>k;
    if(k < 2){
        fout<<k;
    }else{
        fib[1][1] = 0, fib[1][2] = 1;

        mat[1][1] = 0, mat[1][2] = 1;
        mat[2][1] = 1, mat[2][2] = 1;

        mlg[1][1] = 1, mlg[1][2] = 0;
        mlg[2][1] = 0, mlg[2][2] = 1;

        k--;
        while(k > 0){
            if(k & 1)
                prod(2, 2, 2, mlg, mat, mlg); ///mlg = mlg * mat
            prod(2, 2, 2, mat, mat, mat); ///mat = mat^2
            k >>= 1;
        }
        prod(1, 2, 2, fib, mlg, fib); ///fib = fib * mlg
        fout<<fib[1][2];
    }
    return 0;
}
/**
5
2707124
**/