2567. Fibonacci

单点时限: 1.0 sec

内存限制: 256 MB

Given an integer $n$, your goal is to compute the last 4 digits of $F_n$.

$F_n$ is the famous Fibonacci Sequence: $F_0=0, F_1=1; F_n=F_{n-1}+F_{n-2}, \forall n\ge 2$.

输入格式

The input test file will contain multiple test cases. Each test case consists of a single line containing $n$ (where $0 \le n \le 10^9$). The end-of-file is denoted by a single line containing the number $−1$.

输出格式

For each test case, print the last four digits of $F_n$. If the last four digits of Fn are all zeros, print $0$; otherwise, omit any leading zeros (i.e., print $F_n \bmod 10000$).

样例

Input
0
9
999999999
1000000000
-1
Output
0
34
626
6875

27 人解决,34 人已尝试。

33 份提交通过,共有 90 份提交。

4.4 EMB 奖励。

创建: 11 年,7 月前.

修改: 3 年,1 月前.

最后提交: 1 周,4 天前.

来源: Stanford Local 2006

题目标签