2567. Fibonacci

单点时限: 1.0 sec

内存限制: 256 MB

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

is the famous Fibonacci Sequence: .

输入格式

The input test file will contain multiple test cases. Each test case consists of a single line containing (where ). The end-of-file is denoted by a single line containing the number .

输出格式

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

样例

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

20 人解决,25 人已尝试。

23 份提交通过,共有 56 份提交。

4.5 EMB 奖励。

创建: 10 年,9 月前.

修改: 2 年,3 月前.

最后提交: 6 小时前.

来源: Stanford Local 2006

题目标签