Fibonacci ## 来源 Stanford Local 2006 (POJ3070) ## 题目描述 在Fibonacci数列中，$F_0$ = 0, $F_1$ = 1; $F_n$ = $F_{n-1}$ + $F_{n-2}$ , n≥2。例如，Fibonacci数列前10项依次为0, 1, 1, 2, 3, 5, 8, 13, 21, 34。 计算Fibonacci数列的另一个公式是：  给定整数n，你的任务是计算$F_n$的最后4位。 ## 输入描述 输入文件包含多个测试数据。每个测试数据占一行，为整数n，0≤n≤1,000,000,000。输入文件最后一行为-1，代表输入结束。 ## 输出描述 对每个测试数据，输出$F_n$的最后4位（即对10000取余的结果）。 ## 样例输入 ```txt 9 1000000000 -1 ``` ## 样例输出 ```txt 34 6875 ```