## DMOPC '20 Contest 3 P5 - Tower of Power

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Ben is playing around with some tower blocks!

Each of his tower blocks are labelled with an integer, . He stacks them vertically, with at the bottom and at the top.

Ben built his tower and is very proud of it, but is now wondering how powerful it is. As everyone knows, a single tower block's power is equal to its label.

However, in a tower consisting of multiple blocks, the power grows very quickly. In a tower of blocks, the power is equal to . Formally, if is the power of a tower consisting of blocks with labels , then , with .

Ben really wants to know the power of his tower. However, knowing his number might be way too big, he will be happy if you can tell him the power modulo . Can you help him?

is prime.

#### Input Specification

The first line will contain , the number of blocks in Ben's tower, and , the modulus.

The next line will contain integers, the labels on Ben's blocks, from to .

#### Output Specification

Output the power of Ben's tower, mod .

#### Sample Input

3 5
2 3 2

#### Sample Output

2

#### Explanation for Sample Output

The power of Ben's tower is .

Note that you do not need to get the correct output on this case to pass the first subtask.

#### Sample Input 2

3 17
3 5 7

#### Sample Output 2

12

#### Sample Input 3

12 35929738
62525611 69201951 54844075 40933790 64603110 102648769 67604167 54424854 69048209 51968609 55767140 95916210

#### Sample Output 3

9996111