题目描述

盒子里有 $N$ 个球，第 $i$ 个球上写着整数 $A_i$。

只要盒子里至少还有 $2$ 个球，就可以反复进行一次操作：选出两个球，设它们上面的数分别是 $x,y$，得到 $(x^y+y^x)\bmod M$ 分；然后吃掉其中一个球，把另一个放回盒子。

请计算最终总得分的最大可能值。

输入格式

第一行输入 $N,M$。

第二行输入 $A_1,A_2,\ldots,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\le N\le 500$，$2\le M\le 10^9$，$1\le A_i\le M-1$。