마법 곱셈 기계

라스베이거스의 카지노 빅 조에 마법 곱셈 기계(MMM)라는 새 게임기가 들어왔다. 이 기계에는 레버 $N$개와 커다란 빨간 버튼 하나가 달려 있다. 레버마다 $1$ 이상 $M$ 이하의 정수가 하나씩 적혀 있고, $i$번 레버에 적힌 수는 $a_i$이다.

게임을 하려는 사람은 먼저 동전을 투입구에 넣는다. 그다음 레버 몇 개를 골라 당기고, 빨간 버튼을 누른다. 기계는 조명을 깜빡이고 종을 울리며 음악을 연주한 뒤 점수를 알려 준다.

점수는 이렇게 정해진다. 당긴 레버의 번호를 모은 집합을 $S \subseteq \{1, 2, \dots, N\}$라고 하면, 점수는 그 레버에 적힌 수를 모두 곱한 값을 $M$으로 나눈 나머지이다. 레버를 하나도 당기지 않아도 되고, 이때 점수는 $1$이다.

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

어떤 레버를 당기느냐에 따라 점수가 달라진다. 기계의 정보가 주어졌을 때, 받을 수 있는 가장 높은 점수를 구하라.

첫째 줄에 정수 $N$과 $M$이 주어진다. ($1 \le N \le 10000$, $2 \le M \le 1000$)

둘째 줄에 정수 $a_1, a_2, \dots, a_N$이 주어진다. 각 수는 $1$ 이상 $M$ 이하이다.

첫째 줄에 이 기계에서 받을 수 있는 가장 높은 점수를 출력한다.