輸入 \(n\) 個正整數 \(A[1 \cdots n]\)，以及一個質數 \(P\)，請計算 \(A\) 中元素各種組合中，有多少種組合其相乘積除以 \(P\) 的餘數等於 \(1\)。每個元素可以選取或不選取但不可重複選，\(A\) 中的數字可能重複。\(P \leq 1000000009\)，\(0 < n < 37\)。

輸入格式

第一行是 \(n\) 與 \(P\)，第二行 \(n\) 個整數是 \(A[i]\)，同行數字以空白間隔。

輸出格式

滿足條件的組合數，因為數字可能太大，請輸出該組合數除以 \(P\) 的餘數。

範例輸入

5 11
1 1 2 6 10

範例輸出

7