DMOPC '20 Contest 3 P5 - Tower of Power

View as PDF

Submit solution


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

Author:
Problem type

Ben is playing around with some tower blocks!

Each of his N tower blocks are labelled with an integer, a_i. He stacks them vertically, with a_1 at the bottom and a_N 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 N blocks, the power is equal to a_1^{\left(a_2^{(a_3^\cdots)}\right)}. Formally, if P(a_1, a_2, \dots, a_N) is the power of a tower consisting of N blocks with labels a_i, then P(a_1, a_2, \dots, a_n) = a_1^{P(a_2, a_3, \dots, a_N)}, with P(a_N) = a_N.

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 M. Can you help him?

Constraints

1 \le N \le 10^6

2 \le M \le 10^9

1 \le a_i \le 10^9

Subtask 1 [1/15]

1 \le N \le 3

M is prime.

Subtask 2 [14/15]

No additional constraints.

Input Specification

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

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

Output Specification

Output the power of Ben's tower, mod M.

Sample Input 1

3 5
2 3 2

Sample Output 1

2

Explanation for Sample Output 1

The power of Ben's tower is 2^{(3^2)} \equiv 2^9 \equiv 512 \equiv 2 \pmod 5.

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

Comments


  • 3
    Kevy3030  commented on Feb. 1, 2021, 7:41 p.m.

    case 61 :/