정수 수열

면접 대비

시간 제한0.25초메모리 제한512 MB

요약

x, y와 A0, A1의 마지막 두 자리, 그리고 큰 n이 주어질 때 A_n = x*A_{n-1} + y*A_{n-2}로 정의되는 수열의 A_n 마지막 두 자리를 출력한다.

문제

음이 아닌 정수로 이루어진 수열 $A_0, A_1, A_2, A_3, \ldots$ 이 있다.

이 수열은 모든 $n \ge 2$ 에 대해 $A_n = x \times A_{n-1} + y \times A_{n-2}$ 를 만족한다.

$A_0$ 과 $A_1$ 의 마지막 두 자리가 주어질 때, $A_n$ 의 마지막 두 자리를 구하는 프로그램을 작성하시오.

예를 들어 $x = y = 1$ 이고 $A_0 = 0$ , $A_1 = 1$ 이면 수열은 $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$ 이다. $A_{10}$ 의 마지막 두 자리는 $55$ 이다.

첫째 줄에 $x$ , $y$ , $a_0$ , $a_1$ , $n$ 이 공백으로 구분되어 주어진다. ( $1 \le x, y \le 99$ , $0 \le n < 10^8$ )

$a_0$ 과 $a_1$ 은 각각 $A_0$ 과 $A_1$ 의 마지막 두 자리이며, 항상 두 자리로 주어진다. 10보다 작은 값은 앞에 0을 붙여 07처럼 주어진다.

$A_n$ 의 마지막 두 자리를 출력한다. 값이 10보다 작으면 앞에 0을 붙여 07처럼 항상 두 자리로 출력한다.