1053 : 피보나치

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 325 회    시도횟수: 837 회   

피보나치 정수 수열에서 F0 = 0, F1 = 1 이다. 그리고 모든 n ≥ 2 에 대하여 다음과 같이 정의 된다 Fn = Fn-1 + Fn-2 .

 

예를 들어 피보나치수열의 처음 몇 항들은 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 … 이다.

 

피보나치수열의 다른 공식은 다음과 같다.

 

 

 

주어진 정수 n에 대하여 당신이 할 일은 피보나치수열 Fn의 마지막 4자리수를 구하는 것이다.

입력은 여러 개의 test case를 포함할 수 있다.
각 test case는 한 줄에 n (0 ≤ n ≤ 1,000,000,000)을 포함한다.
입력의 끝은 −1을 포함한 한 줄로 주어진다.

각 test case에 대해 ,Fn의 마지막 4자리수를 출력한다. (이를테면 Fn을 10,000 으로 나눈 나머지를 출력한다).
만약 마지막 네 자리가 모두 0 이라면 '0' 을 출력한다. 그렇지 않다면, 모든 leading zero는 제거한다.

0 9 999999999 1000000000 -1

0 34 626 6875

행렬 곱셈은 결합연산이 가능하며 두 2행 2열 행렬의 곱은 아래와 같다:

또 어떤 2행 2열 행렬에 대해서도 행렬의 0승은 단위행렬과 같다.

주 : 단위행렬 - A * B = A 일 경우 B를 단위행렬이라고 한다.