# A Grouping Problem

You are given a set of n integers. You can take k different elements from them to make a group. Two groups will be different if there is at least one element which is not common to both. For example, if there are 4 elements a, b, c, d and you are asked to take two elements then ab, ad, bc, cd are all valid and different groups. A grouping system is complete if for a particular k, number of different groups is the maximum. In the former case, {ab, bc, cd, bd, ad, ac} is a complete grouping system.

For a particular complete grouping system, the fitness is calculated in the following way:

Each group of a grouping system contributes a part - the multiplication of all numbers of that group;

Contribution from all groups are added;

The fitness is equivalent to total contribution mod m, m is the bounding parameter.

In our example, for k = 2, the fitness is `F[2]`

= (ab + bc + cd + bd + ad + ac) mod m. If k = 1, then fitness is `F[1]`

= (a + b + c + d) mod m.

You have to find the complete grouping system with maximum fitness.

## Input

Each test case starts with two positive integer n (2 ≤ n ≤ 1000) and m (1 ≤ m < `2^31`

). In next few lines there will be n positive integers. Each integer will be at best 1000. Input will be terminated by a case where n = m = 0.

## Output

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