P2182
[第六章习题5.1]Fibonacci
描述
我们知道斐波那契数列F0 = 0, F1 = 1, Fn = Fn − 1 + Fn − 2。
求斐波那契数列中的第n项 mod 10000的值。
求斐波那契数列中的第n项 mod 10000的值。
输入
多组数据，每组数据一个n( 0 ≤ n ≤ 1,000,000,000)。
读入以-1结束。
读入以-1结束。
输出
输出Fn mod 10000，若Fn 的未4位都为0，则输出0；否则不要输出前导0.
样例输入
0 9 999999999 1000000000 -1
样例输出
34 626 6875
