子集合乘積(折半枚舉) (AP325 P-2-9)

輸入 \(n\) 個正整數 \(A_1, A_2, \ldots, A_n\)，以及一個質數 \(P\)，請計算 \(A\) 中元素各種組合中，有多少種組合其相乘積除以 \(P\) 的餘數等於 \(1\)。每個元素可以選取或不選取但不可重複選，\(A\) 中的數字可能重複；一個組合至少要選取一個數字。\(P \le 1000000009\)，\(0 < n < 37\)，且假設 \(A\) 中元素皆小於 \(P\)。

輸入格式

第一行是 \(n\) 與 \(P\)，第二行是 \(n\) 個整數 \(A_1, A_2, \ldots, A_n\)，同行數字以空白間隔。

限制

• \(1 \le n \le 36\)。
• \(2 \le P \le 10^9 + 9\)，且 \(P\) 為質數。
• \(1 \le A_i < P\)。

輸出格式

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

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入

5 11
1 1 2 6 10

範例輸出

7

範例說明

乘積除以 \(11\) 餘 \(1\) 的組合有：\((1)\)、\((1)\)、\((1, 1)\)、\((2, 6)\)、\((1, 2, 6)\)、\((1, 2, 6)\)、\((1, 1, 2, 6)\)，共 \(7\) 種。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 2 章 P-2-9，第 59 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。