피보나치 수

피보나치 수열은 $F_0 = 0$, $F_1 = 1$이고, $n \ge 2$일 때 $F_n = F_{n-1} + F_{n-2}$로 정의된다. 예를 들어 수열의 처음 열 개 항은 다음과 같다.

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

피보나치 수는 행렬의 거듭제곱으로도 표현할 수 있다.

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

정수 $n$이 주어질 때 $F_n$의 마지막 네 자리를 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$ 하나가 적힌 한 줄이며, $0 \le n \le 1{,}000{,}000{,}000$을 만족한다. 입력의 끝은 $-1$만 적힌 한 줄로 표시되며, 이 줄은 처리 대상이 아니다.

각 테스트 케이스마다 $F_n$의 마지막 네 자리를 한 줄에 출력한다. 네 자리가 모두 0이면 0을 출력하고, 그렇지 않으면 앞에 오는 0은 생략한다. 즉, $F_n \bmod 10000$을 출력하면 된다.