509003 - 快速求斐波那契数列

【题目描述】快速求斐波那契数列(fibonacci)

斐波那契数列中,F0=0,F1=1,当n≥2时,Fn=Fn – 1+Fn – 2。例如数列的前十项为:0,1,1,2,3,5,8,13,21,34,… 输入一个整数n,输出Fn的最后四位数。

输入

有多组数据,每组数据输入一个整数n(0≤n≤1000000000),-1表示输入结束。

输出

每组数据,输出Fn的最后四位数,如果末尾四位数都为0,则输出0。

样例

输入

0
9
999999999
1000000000
-1

输出

0
34
626
6875
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题