問題文

$N$ 個のトマトが入った箱と空の袋があります。
それぞれのトマトには新鮮度が決められており，$i=1,2,3,...,N$ について $i$ 個目のトマトの新鮮度は $A_i$ です。
元気度が $0$ のAjinoko君は以下を順番に行い，すべてのトマトを箱から袋に移します。

1. 最初に，箱からトマトを $1$ つ選ぶ。選んだトマトを袋に移す。
2. 箱にトマトが入っている限り，次の操作を繰り返し行う。
   • 箱と袋からそれぞれトマトを $1$ つずつ選び，$1 \leq m \leq M$ を満たす整数 $m$ を選ぶ。選んだトマトの新鮮度をそれぞれ $x,y$ とすると，$(x+y)^m$ を $M$ で割ったあまりだけAjinoko君の元気度が上昇する。その後，選んだトマトを両方とも袋に入れる。

全操作終了後におけるAjinoko君の元気度として考えられる最大値を求めてください。

制約

• $2 \leq N \leq 500$
• $2 \leq M \leq 10^{4}$
• $1 \leq A_i \leq 1000$
• 入力はすべて整数

入力

出力

全操作終了後におけるAjinoko君の元気度として考えられる最大値を出力してください。

サンプル1

4 14
1 3 4 5

32

箱に入っているトマトの集合を $BOX$ ，袋に入っているトマトの集合を $BAG$ とします。
はじめは，$BOX=\{1,2,3,4\}, BAG= \emptyset$ です。

1. トマト $2$ を選ぶ。$BOX=\{1,3,4\}, BAG= \{2\}$ になる。
2. 以下の順で操作を行う。
   • 箱からトマト $4$，袋からトマト $2$ を選び，整数 $2$ を選ぶ。元気度は，$(5+3)^2$ を $14$ で割ったあまり $8$ だけ上昇して $0+8=8$ になる。$BOX=\{1,3\}, BAG= \{2,4\}$ になる。
   • 箱からトマト $3$，袋からトマト $4$ を選び，整数 $5$ を選ぶ。元気度は，$(4+5)^5$ を $14$ で割ったあまり $11$ だけ上昇して $8+11=19$ になる。$BOX=\{1\}, BAG= \{2,3,4\}$ になる。
   • 箱からトマト $1$，袋からトマト $3$ を選び，整数 $3$ を選ぶ。元気度は，$(1+4)^3$ を $14$ で割ったあまり $13$ だけ上昇して $19+13=32$ になる。$BOX= \emptyset, BAG= \{1,2,3,4\}$ になる。
   • 箱にトマトが入っていないので終了する。

どのように操作を行っても $32$ より大きい元気度にすることはできないので，答えは $32$ です。

サンプル2

2 10
98 2

0

サンプル3

10 45
861 637 140 471 275 908 672 105 184 405

386