#P0311. 斐波那契

    传统题 3000ms 256MiB

斐波那契

题目描述

在斐波那契数列中,Fib0=0,Fib1=1,Fibn=Fibn1+Fibn2(n>1)Fib_0=0,Fib_1=1,Fib_n=Fib_{n−1}+Fib_{n−2}(n>1)。

给定整数 nn,求 FibnFib_n modmod 1000010000

输入格式

输入包含不超过 200200 组测试用例。

每个测试用例占一行,包含一个整数 nn

当输入用例 n=1n=−1 时,表示输入终止,且该用例无需处理。

输出格式

每个测试用例输出一个整数表示结果。

每个结果占一行。

数据范围

0n2×109.0≤n≤2×10^9.

输入样例:

0
9
999999999
1000000000
-1

输出样例:

0
34
626
6875

相关

在下列比赛中:

思维题