14440번 - 정수 수열

문제

음이 아닌 정수 수열 A₀, A₁, A₂, A₃, ...이 있다.

모든 n ≥ 2에 대해서, A_n = x×A_n-1 + y×A_n-2를 만족한다.

A₀과 A₁의 마지막 두 자리가 주어졌을 때, A_n의 마지막 두 자리를 구하는 프로그램을 작성하시오.

예를 들어, x=y=1이고, A₀ = 0, A₁ = 1인 경우에 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 이다. A₁₀의 마지막 두 자리는 55이다.

입력

첫째 줄에 x, y, a₀, a₁, n이 주어진다. (1 ≤ x, y ≤ 99, 0 ≤ n < 10⁸) a₀과 a₁은 A₀, A₁의 마지막 두 자리이다.

출력

A_n의 마지막 두 자리를 출력한다.

제한

힌트