Migrated from Lutece 278 Fibonacci

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

In the Fibonacci integer sequence, $F_0 = 0, F_1 = 1,$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. For example, the first ten terms of the Fibonacci sequence are:

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \cdots$

An alternative formula for the Fibonacci sequence is

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

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing $n$ (where $0 \leq n \leq 1,000,000,000$).

The end-of-file is denoted by a single line containing the number -1.

Output

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

Samples

0
9
999999999
1000000000
-1

0
34
626
6875

Note

As a reminder, matrix multiplication is associative, and the product of two $2 \times 2$ matrices is given by

Also, note that raising any $2 \times 2$ matrix to the 0th power gives the identity matrix:

The data used in this problem is unofficial data prepared by 695375900. So any mistake here does not imply mistake in the offcial judge data.

Resources

Stanford Local 2006