题目描述

箱の中に $N$ 個のボールが入っており、各ボールには $1$ 以上 $M-1$ 以下の整数が書かれています。 $i\ =\ 1,\ 2,\ \ldots,\ N$ について、$i$ 番目のボールに書かれた整数は $A_i$ です。

高橋君は、箱の中に $2$ 個以上のボールが残っている限り、下記の行動を繰り返します。

• まず、箱の中から $2$ つのボールを任意に選んで取り出す。
• 次に、取り出した $2$ つのボールに書かれた整数をそれぞれ $x,\ y$ とおき、$x^y\ +\ y^x$ を $M$ で割ったあまりに等しい得点を獲得する。
• その後、取り出した $2$ つのボールのうち、任意に選んだ一方を食べ、もう一方を箱の中に戻す。

高橋君が獲得する合計得点としてあり得る最大値を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

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

$1\le n\le 500$。

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. 箱の中から $1$ 番目のボールと $3$ 番目のボールを取り出し、$(4^3\ +\ 3^4)\ \bmod\ 10\ =\ 5$ 点を獲得します。その後、$1$ 番目のボールを食べ、$3$ 番目のボールを箱の中に戻します。その結果、箱の中には $2,\ 3,\ 4$ 番目のボールが残ります。 2. 箱の中から $3$ 番目のボールと $4$ 番目のボールを取り出し、$(3^2\ +\ 2^3)\ \bmod\ 10\ =\ 7$ 点を獲得します。その後、$3$ 番目のボールを食べ、$4$ 番目のボールを箱の中に戻します。その結果、箱の中には $2,\ 4$ 番目のボールが残ります。 3. 箱の中から $2$ 番目のボールと $4$ 番目のボールを取り出し、$(2^2\ +\ 2^2)\ \bmod\ 10\ =\ 8$ 点を獲得します。その後、$2$ 番目のボールを食べ、$4$ 番目のボールを箱の中に戻します。その結果、箱の中には $4$ 番目のボールのみが残ります。 このとき、高橋君が獲得する合計得点は $5\ +\ 7\ +\ 8\ =\ 20$ 点であり、これがあり得る最大値です。