Power

Interview

Time limit1sMemory limit1024 MB

Summary

For each column j, raise the first-row value a_j to the power j+1, add all these diagonal powers, and print the sum modulo m.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

The table has $n + 1$ rows and $n$ columns. The first row holds positive integers. Each of the next $n$ rows holds the powers of the numbers in the first row, in order: the second power, the third power, and so on.

In the table below, $n = 4$ . The rows hold the powers of 3, 5, 2, and 1 up to the fifth power.


3	5	2	1
9	25	4	1
27	125	8	1
81	625	16	1
243	3125	32	1

Write a program power that adds the numbers on the diagonal (the bold cells) and prints the sum modulo $m$ . For the example with $m = 3$ , the sum is 9 + 125 + 16 + 1 = 151. The remainder of 151 divided by 3 is 1, so the answer is 1.

Input

The first line contains the positive integers $n$ and $m$ . The second line contains the $n$ numbers of the first row, separated by spaces.

Output

Print the sum of the diagonal numbers modulo $m$ as a single integer.

Constraints

$n \le 1000000$ , $m \le 10000000$ . The numbers in the first row are positive integers less than 100000.

Examples1

Example 1
Input
```
4 3
3 5 2 1
```
Expected output
```
1
```