Задача группирования
Имеется множество из n целых чисел. Из любых k разных элементов Вы можете составить группу. Две группы считаются разными, если у них имеется хотя бы один не общий элемент. Например, если имеются 4 элемента a, b, c, d и Вам необходимо составить группы из двух элементов, то возможными допустимыми группами будут ab, ad, bc, cd. Систему групп будем называть полной для заданного k, если количество групп в ней максимально возможное. Например, для предыдущего примера {ab, bc, cd, bd, ad, ac} является полной системой групп.
Удобство полной системы групп будем вычислять следующим образом:
Каждая группа делает свой вклад в систему – произведение чисел в группе;
Вклады всех групп складываются;
Удобство системы эквивалентно общему вкладу 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 и не обрабатывается.
Выходные данные
Для каждого теста в отдельной строке вывести максимальное значение удобства среди всех полных систем групп.