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取余的结果）。

样例输入

9
1000000000
-1

样例输出

34
6875