문제
피보나치 정수 수열에서
예를 들어 피보나치수열의 처음 몇 항들은 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 … 이다.
피보나치수열의 다른 공식은 다음과 같다.
\left[\begin{matrix} F_{n+1} & F_n \\ F_n & F_{n-1} \\ \end{matrix}\right] =
\left[\begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix}\right]^n =
\underbrace{
\left[\begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix}\right]
\left[\begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix}\right]
\cdots
\left[\begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix}\right]}_{n \; times}
주어진 정수 n에 대하여 당신이 할 일은 피보나치수열
입력
입력은 여러 개의 test case를 포함할 수 있다.
각 test case는 한 줄에
입력의 끝은 −1을 포함한 한 줄로 주어지며 최대 50개를 초과하지 않는다.
출력
각 test case에 대해 ,
만약 마지막 네 자리가 모두 0 이라면 '0' 을 출력한다. 그렇지 않다면, 모든 leading zero는 제거한다.
예제1
입력
0
9
999999999
1000000000
-1
출력
0
34
626
6875
힌트