Given integers A[1]
, A[2]
, ..., A[n]
and number m.
Choose such subset of numbers A[1]
, A[2]
, ..., A[n]
so that their product taken modulo m is maximum.
First line contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 10000). Second line contains n integers A[1]
, A[2]
, ..., A[n]
(0 ≤ A[i]
≤ 10000).
Print in the first line numbers p and k - the product of chosen numbers by modulo m and the number of chosen numbers. Print in the second line k numbers B[1]
, B[2]
, ..., B[k]
- the indexes of chosen numbers. The indexes must be pairwise different. If there are multiple answers with maximum p, print any of them.