Cho ~F(x) = ax + b~ và dãy số ~S = \{S_1, S_2, \dots, S_n\}~ được xác định như sau:

• ~S_1 = c~
• ~S_i = F(S_{i-1}) \pmod{100}~ với ~2 \le i \le n~

Hãy tìm số lớn thứ ~K~ của ~S~.

Yêu cầu: Xác định giá trị lớn thứ ~K~ trong dãy ~S~ đã cho.

Input

• Dòng đầu ghi 3 số nguyên dương ~a, b, c~ (~a, b \le 10^9~, ~c < 100~).
• Dòng tiếp theo ghi 2 số nguyên dương ~N, K~ (~K \le N \le 10^7~).

Output

• In ra một dòng duy nhất chứa một số nguyên là số lớn thứ ~K~ của mảng ~S~.

Sample Input 1

3 1 4
5 3

Sample Output 1

21