Fibonacci

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

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

An equivalent formulation uses matrix exponentiation:

$\begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n$

Given an integer $n$, compute the last four digits of $F_n$.

The input contains multiple test cases. Each test case is a single line holding an integer $n$ with $0 \le n \le 1{,}000{,}000{,}000$. The input ends with a single line containing $-1$, which is not part of the data.

For each test case, print the last four digits of $F_n$ on its own line. If those four digits are all zero, print 0; otherwise omit any leading zeros. In other words, print $F_n \bmod 10000$.