Fibonacci Sequence

Problem Description

The Fibonacci sequence is defined by the recurrence $F_n = F_{n-1} + F_{n-2}$, with $F_1 = F_2 = 1$.

When $n$ is large, $F_n$ is also very large. We now want to know the remainder of $F_n$ divided by $10007$.

Input Format

One integer $n$ ($1 \le n \le 10^6$).

Output Format

Output one line containing an integer: the remainder of $F_n$ divided by $10007$.

Sample Input 1

10

Sample Output 1

55

Sample Input 2

22

Sample Output 2

7704

Hint

In this problem the answer is the remainder of $F_n$ divided by $10007$, so we only need to compute that remainder — there is no need to first compute the exact value of $F_n$ and then divide it by $10007$ to take the remainder. Computing the remainder directly is usually much simpler than computing the original number first and then taking the remainder.