#include<fstream>	
#include<bits/stdc++.h>


using namespace std;
const int mod=666013;

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

int a[2][2] = {{0, 1}, {1, 1}};
int i[2][2] = {{1, 0}, {0, 1}};

//copy matrix c into matrix a
void copy(int a[2][2], int c[2][2]) {
    a[0][0] = c[0][0];
    a[0][1] = c[0][1];
    a[1][0] = c[1][0];
    a[1][1] = c[1][1];
}

//multiply 2 matrixes 
void multiply(int a[2][2], int b[2][2]) {
    int c[2][2];
    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] = (c[i][j] + (1LL * a[i][k] * b[k][j])) % mod;
        }
    }

    copy(a, c);
}

void log_power(int n) {
    while (n > 0){
        if (n % 2 == 1)
            multiply(i, a);
        
        multiply(a, a);
        n = n / 2;
    }
}

int main(){


    int n;
    fin >> n;
    if (n <= 1)
        fout << n;

    log_power(n - 1);
    fout << i[1][1];

    return 0;
}