Product of differences#9889

Product of differences

1 second

128 megabytes

Easy

Array of integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n is given. Find the product

1 \leq i < j \leq n \prod ∣ a_{i} - a_{j} ∣

\prod_{\substack{1 \le i < j \le n}}|a_i − a_j|

If you are not familiar with short notation, this product equals to

∣ a_{1} - a_{2} ∣ \times ∣ a_{1} - a_{3} ∣ \times \dots \times ∣ a_{1} - a_{n} ∣ \times ∣ a_{2} - a_{3} ∣ \times ∣ a_{2} - a_{4} ∣ \times \dots \times ∣ a_{2} - a_{n} ∣ \times \dots \times ∣ a_{n - 1} - a_{n} ∣

|a_1 − a_2| \times |a_1 − a_3| \times \ldots \times |a_1 − a_n| \times |a_2 − a_3| \times |a_2 − a_4| \times \ldots \times |a_2 − a_n| \times \ldots \times |a_{n−1} − a_n|

In other words, this is the product of $∣ a_{i} - a_{j} ∣$ |a_i − a_j| for all $1 \leq i < j \leq n$ 1 \le i < j \le n.

As the result will be very big, find it modulo $m$ .

Input

First line contains two integers $n (n \leq 1 0^{5})$ n\:(n \le 10^5) and $m (m \leq 1000)$ m\:(m \le 1000). Next line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n} (0 \leq a_{i} \leq 1 0^{9})$ a_1, a_2, \ldots, a_n\:(0 \le a_i \le 10^9).

Output

Print the value of the product modulo $m$ .

Examples

Example 1

a_{1}, a_{2}, \dots, a_{n}

1 \leq i < j \leq n \prod ∣ a_{i} - a_{j} ∣

∣ a_{1} - a_{2} ∣ \times ∣ a_{1} - a_{3} ∣ \times \dots \times ∣ a_{1} - a_{n} ∣ \times ∣ a_{2} - a_{3} ∣ \times ∣ a_{2} - a_{4} ∣ \times \dots \times ∣ a_{2} - a_{n} ∣ \times \dots \times ∣ a_{n - 1} - a_{n} ∣

∣ a_{i} - a_{j} ∣

1 \leq i < j \leq n

n (n \leq 1 0^{5})

m (m \leq 1000)

a_{1}, a_{2}, \dots, a_{n} (0 \leq a_{i} \leq 1 0^{9})