J21 实践-5 不可能的计算

题目描述

为了成为oimao之王，库罗尼必须解决以下问题。

他得到 $n$ 个数字$a_1,a_2,\ldots,a_n$。帮助库罗尼计算 $\prod_{1\le i<j\le n}|a_i-a_j|$， 如果结果可能非常大，请将其以 $m$ 为模数输出。

如果您不熟悉短符号，$\prod_{1\le i<j\le n}|a_i-aj|$等于$|a_1-a_2||a_1-a_3|\ldots |a_1-a_n||a_2-a_3||a_2-a_4||a_1-a_n| \ldots |a_2-a_n| \ldots |a_{n-1}-a_n|$。换句话说，这是表示所有$1\le i<j\le n$ 的$|a_i−a_j|$ 的乘积。

输入格式

第一行包含两个整数 $n$，$m$ -序列的长度和模数。

第二行包含n个整数，$a_1,a_2,\ldots,a_n$。

输出格式

输出 $\prod_{1\le i<j\le n}|a_i-aj| \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

样例分析

样例1：$|8 - 5| = 3 \equiv 3 \bmod 10$

样例2：$|1 - 4|\cdot|1 - 5|\cdot|4 - 5| = 3\cdot 4 \cdot 1 = 12 \equiv 0 \bmod 12$

样例3：$|1 - 4|\cdot|1 - 9|\cdot|4 - 9| = 3 \cdot 8 \cdot 5 = 120 \equiv 1 \bmod 7$

数据范围

对于 $100\%$ 的数据：$2\le n \le 2\times 10^5$，$1\le m \le 1000$，$0 \le a_i \le 10^9$。