题面翻译

有 $n$ 个数 $a_i$，你每次可以选出两个数 $a_i$ 和 $a_j$，获得 $(a_i^{a_j}+a_j^{a_i}) \bmod M$ 分，并选择这两个数中的一个数删掉，求最大得分。

$1\le n\le 500$。

输入格式

第一行输入 $n$ 和 $m$

接下来一行输入 $n$ 个整数代表 $a_1,a_2,\cdots,a_n$

输出格式

输出和一个整数代表答案

4 10
4 2 3 2

20

20 100
29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

1733

提示

• $2\ \leq\ n\ \leq\ 500$
• $2\ \leq\ m\ \leq\ 10^9$
• $1\ \leq\ a_i\ \leq\ m-1$

Sample Explanation 1

考虑下面的情况。下面的 $X \bmod Y$ 表示非负整数 $X$ 除以正整数 $Y$ 的余数。

1. 从盒子中取出第一个和第三个球，得 $(4^3 + 3^4) \bmod 10 = 5$ 分。然后吃掉第一个球，将第三个球放回盒子。现在，盒子里有第二个、第三个和第四个球。
2. 从盒子中取出第三个和第四个球，得 $(3^2 + 2^3) \bmod 10 = 7$ 分。然后，吃掉第三个球，将第四个球放回盒子。现在，盒子里有第二个和第四个球。
3. 从盒子中取出第二个和第四个球，得 $(2^2 + 2^2) \bmod 10 = 8$ 分。然后，吃掉第二个球，将第四个球放回盒子。现在，盒子里只有第四个球。

在这里，高桥一共得到了 $5 + 7 + 8 = 20$ 分，这是可能得到的最大值。