Чтобы стать королем Codeforces, Курони должен решить следующую задачу.
Ему даны \(n\) чисел \(a_1, a_2, \dots, a_n\). Помогите Курони посчитать \(\prod_{1\le i<j\le n} |a_i - a_j|\). Так как ответ может быть очень большим, посчитайте его по модулю \(m\).
Если вы не знакомы с короткой формой записи, \(\prod_{1\le i<j\le n} |a_i - a_j|\) равно \(|a_1 - a_2|\cdot|a_1 - a_3|\cdot\) \(\dots\) \(\cdot|a_1 - a_n|\cdot|a_2 - a_3|\cdot|a_2 - a_4|\cdot\) \(\dots\) \(\cdot|a_2 - a_n| \cdot\) \(\dots\) \(\cdot |a_{n-1} - a_n|\). Другими словами, это произведение \(|a_i - a_j|\) по всем \(1\le i < j \le n\).
Выходные данные
Выведите единственное число — \(\prod_{1\le i<j\le n} |a_i - a_j| \bmod m\).
Примечание
В первом примере, \(|8 - 5| = 3 \equiv 3 \bmod 10\).
Во втором примере, \(|1 - 4|\cdot|1 - 5|\cdot|4 - 5| = 3\cdot 4 \cdot 1 = 12 \equiv 0 \bmod 12\).
В третьем примере, \(|1 - 4|\cdot|1 - 9|\cdot|4 - 9| = 3 \cdot 8 \cdot 5 = 120 \equiv 1 \bmod 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 10
8 5
|
3
|
|
2
|
3 12
1 4 5
|
0
|
|
3
|
3 7
1 4 9
|
1
|