#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>

#include <iomanip>

#define int long long

using namespace std;

string filename = "kfib";

#ifdef LOCAL
    ifstream fin("input.in");
    ofstream fout("output.out");
#else
    ifstream fin(filename + ".in");
    ofstream fout(filename + ".out");
#endif

const int NMAX = 2;
const int MOD = 666013;

int trans[NMAX + 1][NMAX + 1];
int ans[NMAX + 1][NMAX + 1];

int aux[NMAX + 1][NMAX + 1];
void mult(int mat1[NMAX + 1][NMAX + 1], int mat2[NMAX + 1][NMAX + 1], int prod[NMAX + 1][NMAX + 1], int n, int m, int p){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= p; j++){
            aux[i][j] = 0;
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= p; j++){
            for(int k = 1; k <= m; k++){
                (aux[i][j] += (mat1[i][k] * mat2[k][j]) % MOD) %= MOD;
            }
        }
    }

    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= m; j++){
            prod[i][j] = aux[i][j];
        }
    }
}


int rez[NMAX + 1][NMAX + 1];
void exp(int m[NMAX + 1][NMAX + 1], int n, int exp){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            rez[i][j] = 0;
        }
    }

    for(int i = 1; i <= n; i++){
        rez[i][i] = 1;
    }

    while(exp != 0){
        if(exp % 2 == 1){
            mult(rez, m, rez, n, n, n);
        }
        mult(m, m, m, n, n, n);
        exp /= 2;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            m[i][j] = rez[i][j];
        }
    }
}

signed main(){

    int n;
    fin >> n;

    ans[1][1] = 0, ans[1][2] = 1;
    trans[1][1] = 0, trans[1][2] = 1;
    trans[2][1] = 1, trans[2][2] = 1;

    exp(trans, 2, n - 1);
    mult(ans, trans, ans, 1, 2, 2);

    fout << ans[1][2] << '\n';

    return 0;
}