J. Krosh and order-2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Krosh has an array of $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ and some number $$$m$$$. He determines beauty $$$F$$$ of the sequence $$$a_1, a_2, ..., a_n$$$ in the following way: $$$F(A) = a_1 $$$ $$$mod$$$ $$$m$$$ $$$+ a_2 ^ 2$$$ $$$mod$$$ $$$m$$$ $$$+ a_3 ^ 3$$$ $$$mod$$$ $$$m$$$ + ... + $$$a_n ^ n$$$ $$$mod$$$ $$$m$$$(number above is the power) where $$$x$$$ $$$mod$$$ $$$m$$$ is reminder from division of $$$x$$$ to $$$m$$$. Krosh wants to reorder elements in his array in a way that maximizes it's beauty. Help him to determine maximum possible beauty of the array.

Input

In the first line you are given two numbers $$$1 \le n \le 10^5$$$ - amount of elements in the array and $$$2 \le m \le 4$$$ - number for determining the beauty. In the next line you are given $$$n$$$ numbers $$$0 \le a_i \lt m$$$.

Output

Output the answer for the problem.

Examples
Input
4 4
1 0 3 3
Output
7
Input
5 3
1 2 1 0 1
Output
5