A Grouping Problem#1525

A Grouping Problem

1 second

128 megabytes

Hard

You are given a set of $n$ integers. You may choose $k$ distinct elements from this set to form a group. Two groups are considered different if there exists at least one element that is present in one group but not in the other. For example, if the set contains $4$ elements $a, b, c, d$ a, b, c, d, and you are asked to choose two elements, then $ab, a c, a d, b c, b d$ ab, ac, ad, bc, bd, and $c d$ are all valid and distinct groups.

A grouping system is called complete if, for a given $k$ , the number of different groups is maximized. In this example, the set ${ab, a c, a d, b c, b d, c d}$ \{ab, ac, ad, bc, bd, cd\} forms a complete grouping system.

For a particular complete grouping system, the fitness is computed as follows:

Each group contributes the product of all numbers in that group;
All group contributions are summed;
The fitness is defined as the total contribution $mod m$ , where $m$ is the bounding parameter.

In the example above, for $k = 2$ k = 2, the fitness is

F_{2} = (ab + a c + a d + b c + b d + c d) mod m

F_2 = (ab + ac + ad + bc + bd + cd) \bmod\ m

If $k = 1$ k = 1, the fitness is

F_{1} = (a + b + c + d) mod m

F_1 = (a + b + c + d) \bmod\ m

Your task is to determine the complete grouping system that yields the maximum possible fitness.

Input

Each test case starts with two positive integers $n (2 \leq n \leq 1000)$ n~(2 \le n \le 1000) and $m (1 \leq m < 2^{31})$ m~(1 \le m < 2^{31}). The next line contains $n$ positive integers, each at most $1000$ . The last test case contains $n = m = 0$ n = m = 0 and should not be processed.

Output

For each test case, print a single line containing the maximum possible fitness for a grouping system.

Examples

Example 1

Loading

a, b, c, d

ab, a c, a d, b c, b d

{ab, a c, a d, b c, b d, c d}

k = 2

F_{2} = (ab + a c + a d + b c + b d + c d) mod m

k = 1

F_{1} = (a + b + c + d) mod m

n (2 \leq n \leq 1000)

m (1 \leq m < 2^{31})

n = m = 0