Имеется множество из 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 удобство равно F2 = (ab + bc + cd + bd + ad + ac) mod m. При k = 1 удобство равно F1 = (a + b + c + d) mod m.

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

Входные данные

Каждый тест начинается двумя натуральными числами n (2 ≤ n ≤ 1000) и m (1 ≤ m < 231). Следующая строка содержит n натуральных чисел, каждое из которых не больше 1000. Последний тест содержит n = m = 0 и не обрабатывается.

Выходные данные

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