Description

Original Source: POJ 3070

We know the Fibonacci sequence is defined as $F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ for $n \geq 2$.

Compute $F_n \bmod 10^4$.

Input Format

Multiple test cases. Each case consists of a single line containing an integer $n$.

Input ends with $-1$.

Output Format

For each test case, output $F_n \bmod 10^4$.

Sample 1

0
9
999999999
1000000000
-1

0
34
626
6875

Constraints and Notes

For all test cases, $0 \le n \le 10^9$.