Description

问题描述 Fibonacci数列的递推公式为：$Fn=Fn-1+Fn-2$，其中$F_1$=$F_2$=$1$。 当$n$比较大时，$F_n$也非常大，现在我们想知道，$F_n$除以10007的余数是多少. ($1 < = n < = 1,000,000$).

Format

Input

输入格式 输入包含一个整数n。

Output

输出格式 输出一行，包含一个整数，表示$F_n$除以10007的余数。

Samples

10

55

22

7704