2567. Fibonacci

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


24 人解决，31 人已尝试。

27 份提交通过，共有 81 份提交。

4.6 EMB 奖励。