Magic Multiplying Machine

The Las Vegas casino Big Jo has a new game machine, the Magic Multiplying Machine (MMM). The machine has $N$ levers and one large red button. Every lever carries an integer between $1$ and $M$, and lever $i$ carries the number $a_i$.

A player who wants to play drops a coin into the slot. She then picks some of the levers and pulls them, and finally presses the big red button. The machine blinks its lights, rings its bells, plays a tune, and then announces the score.

The score is decided like this. Let $S \subseteq \{1, 2, \dots, N\}$ be the set of levers the player pulled. The score is the product of the numbers written on those levers, taken modulo $M$. Pulling no lever at all is allowed, and then the score is $1$.

$\text{score} = \left( \prod_{i \in S} a_i \right) \bmod M$

Different choices of levers give different scores. Given the description of one machine, find the highest score a player can reach.

The first line contains two integers $N$ and $M$ ($1 \le N \le 10000$, $2 \le M \le 1000$).

The second line contains $N$ integers $a_1, a_2, \dots, a_N$. Each of them is between $1$ and $M$.

Print one integer on the first line, the highest score that can be obtained on this machine.