Добуток чисел

Задано цілі числа A[1], A[2], ..., A[n] та число m.

Виберіть таку підмножину чисел A[1], A[2], ..., A[n], щоб їхній добуток, взятий за модулем m, був максимальним.

Вхідні дані

У першому рядку задано два цілих числа n та m (1 ≤ n ≤ 100, 1 ≤ m ≤ 10000). У другому рядку записано n цілих чисел A[1], A[2], ..., A[n] (0 ≤ A[i] ≤ 10000).

Вихідні дані

У першому рядку виведіть числа p та k - добуток вибраних чисел по модулю m та кількість вибраних чисел, відповідно. У другому рядку виведіть k чисел B[1], B[2], ..., B[k] - номери вибраних чисел. Номери повинні бути попарно різні. Якщо відповідей з максимальним p декілька, можна виводити довільну з них.

Приклади