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

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

Зручність повної системи груп будемо обчислювати наступним чином:

1. Кожна група робить свій внесок у систему – добуток чисел у групі;

2. Внески усіх груп додаються;

3. Зручність системи еквівалентно загальному внеску mod m, де m - обмежуючий параметр

В нашому прикладі для k = 2 зручність дорівнює F[2] = (ab + bc + cd + bd + ad + ac) mod m. При k = 1 зручність дорівнює F[1] = (a + b + c + d) mod m.

Вам слід знайти повну систему груп з максимальною зручністю.

Вхідні дані

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

Вихідні дані

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

Приклади