题目描述

一个盒子中装有 $N$ 个球，每个球上写着一个介于 $1$ 和 $M-1$ 之间的整数。对于 $i=1,2,\ldots,N$，第 $i$ 个球上写着整数 $A_i$。

当盒子中剩下两个或更多的球时，高桥会重复以下操作：

• 首先，任意选择两个球。
• 然后，获得得分为 $x^y + y^x$ 对 $M$ 求余后的余数，其中 $x$ 和 $y$ 分别是两个球上的整数。
• 最后，随机选择其中一个球吃掉，并将另一个球放回盒子中。

输出高桥可能获得的最大总得分。

约束条件

• $2 \leq N \leq 500$
• $2 \leq M \leq 10^9$
• $1 \leq A_i \leq M-1$
• 输入中的所有值都是整数。

输入

输入通过标准输入给出，格式如下：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$

输出

输出答案。

示例输入 1

4 10
4 2 3 2

示例输出 1

20

考虑以下场景。下面的 $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$ 分，这是可能的最大值。

示例输入 2

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

示例输出 2

1733