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:

1. Each group of a grouping system contributes a part - the multiplication of all numbers of that group;
2. Contribution from all groups are added;
3. The fitness is equivalent to total contribution mod m, m is the bounding parameter.

In our example, for k = 2, the fitness is F2 = (ab + bc + cd + bd + ad + ac) mod m. If k = 1, then fitness is F1 = (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 < 231). 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.