Overflow and Modulo

Integer overflow is a phenomenon where an integer variable leaves its representable range during a computation and ends up holding an unintended value. It happens often in languages such as C, C++, and Java, where the size of a variable is fixed together with its type.

A typical 4-byte integer type can represent positive integers up to $2^{31}-1 = 2147483647$. What happens if two 4-byte integer variables holding $1000000$ and $1000000$ are multiplied? The exact product is $1000000 \times 1000000 = 1000000000000$, but since that value already exceeds the representable range, the desired result does not come out, and the value is stored as some other value the type can represent.

The first remedy is to use an integer type with a wider range. For example, long long in C and C++ or long in Java can represent every integer from $-2^{63}$ up to $2^{63}-1$. There are also languages such as Python whose types have no memory limit, so overflow needs no special handling.

In this problem, $N$ integers are multiplied. A product of integers grows so fast that it can easily exceed what an integer variable can represent. So use the following congruence and compute the remainder of the product of the $N$ integers divided by $M$.

$(A \times B) \bmod M = ((A \bmod M) \times (B \bmod M)) \bmod M$

Given $N$ integers and $M$, write a program that computes the remainder of the product of all the integers divided by $M$.

The first line contains the count $N$ of integers to multiply ($1 \le N \le 100$) and $M$ ($1 \le M \le 2147483647$). The second line contains the $N$ integers $a_i$ ($1 \le a_i \le 2147483647$) separated by spaces on one line.

Print, on one line, the remainder of the product of the $N$ integers divided by $M$.