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

33 人解决,46 人已尝试。

40 份提交通过,共有 126 份提交。

4.6 EMB 奖励。

创建: 15 年,6 月前.

修改: 7 年前.

最后提交: 1 年前.

来源: Stanford Local 2006

题目标签