要成为 Codeforces 之王,Kuroni 必须解决以下问题。
他得到了 $$$n$$$ 数字 $$$a_1, a_2, \dots, a_n$$$。帮助 Kuroni 计算 $$$\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|$$$。换句话说,这是所有 $$$1\le i < j \le n$$$ 的 $$$|a_i - a_j|$$$ 的乘积。
输入
第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$2\le n \le 2\cdot 10^5$$$, $$$1\le m \le 1000$$$) — 数字的个数和模数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。
输出
输出单个数字 — $$$\prod_{1\le i<j\le n} |a_i - a_j| \bmod m$$$。
示例
输入 #1
2 10 8 5
输出 #1
3
输入 #2
3 12 1 4 5
输出 #2
0
输入 #3
3 7 1 4 9
输出 #3
1
注意
在第一个示例中,$$$|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$$$。