The Fibonacci numbers F_{n} are defined as follows:
F_{n} =  ⎧ ⎪ ⎨ ⎪ ⎩ 

Therefore, the first Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
For every given natural number n, compute F_{n} mod10^{8} + 7.
Input
Input consists of several n. Assume 0 ≤ n ≤ 10^{5}.
Output
For every given n, print F_{n} mod10^{8} + 7.
Input
0 1 10 100000
Output
0 1 55 33178829