Добуток різниць#9889

Добуток різниць

1 секунда

128 мегабайтів

Легка

Дано масив цілих чисел $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n. Потрібно обчислити добуток

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

\prod_{\substack{1 \le i < j \le n}}|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_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|

Іншими словами, це добуток $∣ a_{i} - a_{j} ∣$ |a_i − a_j| для всіх $1 \leq i < j \leq n$ 1 \le i < j \le n.

Оскільки результат буде великим, обчисліть його за модулем $m$ .

Вхідні дані

Перший рядок містить два цілих числа $n (n \leq 1 0^{5})$ n\:(n \le 10^5) і $m (m \leq 1000)$ m\:(m \le 1000). Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, ..., a_{n} (0 \leq a_{i} \leq 1 0^{9})$ a_1, a_2, ..., a_n\:(0 \le a_i \le 10^9).

Вихідні дані

Виведіть значення добутку за модулем $m$ .

Приклади

Приклад 1

a_{1}, a_{2}, ..., 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}, ..., a_{n} (0 \leq a_{i} \leq 1 0^{9})