← 返回题目列表

Codeforces · 1305/C

C. 库罗尼和不可能的计算

中文机器翻译题面 查看原题

要成为 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$$$。