1151: 求斐波拉契数列加强版

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：22 Solved：7

Description

斐波那契数列是指这样的数列:数列的第一个和第二个都为1，接下来的每个数都等于前两个数之和。

也就是 f(n) = f(n-1) + f(n-2)

给出一 个正整数n，要求斐波那契数列中第n个数是多少。由于结果较大，仅需输出数列对1008610010取余的结果。

也就是 f(n) = (f(n-1) + f(n-2))%1008610010

数据规模 0 <= n <= 1,000,000,000

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

多组测试用例，直到文件末尾

每组测试用例一行，仅包含一个数N

Output

输出对应的f(n)

Sample Input Copy 

1
2
3
10

Sample Output Copy 

1
1
2
55

Source/Category