Задача групування#1525

Задача групування

1 секунда

128 мегабайтів

Складна

Дано множину з $n$ цілих чисел. Ви можете обрати з цієї множини $k$ різних елементів, щоб сформувати групу. Дві групи вважаються різними, якщо існує хоча б один елемент, який присутній в одній групі, але відсутній в іншій. Наприклад, якщо множина складається з $4$ елементів $a, b, c, d$ a, b, c, d, і потрібно обрати два елементи, то $ab, a c, a d, b c, b d$ ab, ac, ad, bc, bd і $c d$ є всіма коректними та різними групами.

Система групування називається повною, якщо для заданого $k$ число різних груп максимально. В цьому прикладі множина ${ab, a c, a d, b c, b d, c d}$ \{ab, ac, ad, bc, bd, cd\} утворює повну систему групування.

Для деякої повної системи групування її оцінка (fitness) обчислюється наступним чином:

кожна група вносить вклад, рівний добутку всіх чисел у цій групі;
усі вклади груп сумуються;
підсумкова оцінка визначається як сумарний вклад $mod m$ , де $m$ — обмежуючий параметр.

У наведеному вище прикладі, для $k = 2$ k = 2, оцінка дорівнює

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

Якщо $k = 1$ k = 1, то оцінка дорівнює

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

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

Ваше завдання — визначити повну систему групування, яка дає максимально можливу оцінку.

Вхідні дані

Кожен тест починається з двох додатних цілих чисел $n (2 \leq n \leq 1000)$ n~(2 \le n \le 1000) і $m (1 \leq m < 2^{31})$ m~(1 \le m < 2^{31}). Наступний рядок містить $n$ натуральних чисел, кожне з яких не більше $1000$ . Останній тест містить $n = m = 0$ n = m = 0 і не обробляється.

Вихідні дані

Для кожного тесту виведіть в окремому рядку максимально можливу оцінку для системи групування.

Приклади

Приклад 1