#include <stdio.h>
#define MODULO 666013;
//algortim pentru inmultirea matricilor
void matrixMultiply(long long int A[2][2], long long int B[2][2], long long int result[2][2]) {
long long int temp[2][2];
int i, j, k;
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
temp[i][j] = 0;
for (k = 0; k < 2; k++) {
temp[i][j] += (A[i][k] * B[k][j]) % MODULO;
temp[i][j] %= MODULO;
}
}
}
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
result[i][j] = temp[i][j];
}
}
}
//ridicarea la putere a unei matrici, cu un exponent dat
void matrixPower(long long int A[2][2], long long int exponent) {
long long int resultArray[2][2] = {{1, 0}, {0, 1}};
long long int baseArray[2][2];
int i, j, k;
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
baseArray[i][j] = A[i][j];
}
}
while (exponent > 0) {
if (exponent % 2 == 1) {
matrixMultiply(resultArray, baseArray, resultArray);
}
matrixMultiply(baseArray, baseArray, baseArray);
exponent /= 2;
}
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
A[i][j] = resultArray[i][j];
}
}
}
long long int getFibonacciModulo(long long int kTh) {
long long int kThFibonacciElement[2][2] = {{1, 1}, {1, 0}};
matrixPower(kThFibonacciElement, kTh - 1);
return kThFibonacciElement[0][0];
}
int main() {
long long int kTh;
freopen("kfib.in", "r", stdin);
freopen("kfib.out", "w", stdout);
scanf("%lld", &kTh);
long long int result = getFibonacciModulo(kTh);
printf("%lld\n", result);
return 0;
}