#include <bits/stdc++.h>
using namespace std;

const int MOD = 666013;
int k;

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

void mult_mat(int a[2][2], int b[2][2], int rez[2][2]){
    for(int i = 0;i < 2;++i)
        for(int j = 0;j < 2;++j){
            rez[i][j] = 0;
            for(int k = 0;k < 2;++k)
                rez[i][j] = ((1LL * a[i][k] * b[k][j]) % MOD + rez[i][j]) % MOD;
        }
}

void copy_mat(int a[2][2], int b[2][2]){
    for(int i = 0;i < 2;++i)
        for(int j = 0;j < 2;++j)
            a[i][j] = b[i][j];
}

int lg_put(){
    int p = k - 2;
    int rez[2][2] = {{1, 1}, {1,0}};
    int a[2][2] = {{1, 1}, {1, 0}};
    int aux[2][2];
    while(p){
        if(p % 2 == 1){
            mult_mat(rez,a,aux);
            copy_mat(rez,aux);
        }
        mult_mat(a, a, aux);
        copy_mat(a, aux);
        p /= 2;
    }
    return rez[0][0];
}

int main(){

    fin >> k;
    if(k <= 1)
        fout << 1;
    else
        fout << lg_put();
    return 0;
}