Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3283
Mathematics II

Time Limit: 10 Seconds      Memory Limit: 32768 KB

The problem is simple. You should calculate the following formula. When D = 1234567.

Input

There will be no more than 5 test cases.
The first line of each case is three integers N, B, C (1 ≤ N ≤ 50, 1 ≤ B ≤ 10100000, 1 ≤ C ≤ 100).
The second line will be N integers a1 to aN (1 ≤ ai ≤ 10000).

Output

Print the result for each case.

Sample Input

3 5 37
3 4 5

Sample Output

120

Hint

The sample is ((3*4*5)^5%37 + (3*4)^5%37 + (3*5)^5%37 + (4*5)^5%37 + 3^5%37 + 4^5%37 + 5^5%37) % 1234567.
Author: ZHUANG, Junyuan
Source: ZOJ Monthly, December 2009
Submit    Status