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

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 fitnessisF1 =(a+b+c+d)modM. Here, in this problem 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. Sample Input 4 10 1234 4 100 1234 46 1234 00 Sample Output 5 50 5