#include <iostream>
#include <fstream>
#include <cstring>
#define BEAST 666013

using namespace std;

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

int f[3][3], result[3][3];
int kth;
long long rez;

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

void to_power(int power){
	int aux[3][3];
	result[0][0] = result[1][1] = 1;

	int i;
	for(i = 0; (1 << i) <= power; i++){
		if(power & (1 << i)){ // bitul i al lui power este 1
			mult_mat(result, f, aux);
			memcpy(result, aux, sizeof(aux));
		}
		mult_mat(f, f, aux);
		memcpy(f, aux, sizeof(aux));
	}
}

int main(){

	fin >> kth;
	f[0][0] = 0;
	f[1][1] = f[1][0] = f[0][1] = 1;

	to_power(kth - 1);

	fout << result[1][1] << '\n';

	return 0;	
}