子集合乘積 (AP325 P-1-7)

輸入 \(n\) 個正整數，請計算其中有多少組合的相乘積除以 \(P\) 的餘數為 \(1\)。每個數字可以選取或不選取但不可重複選，輸入的數字可能重複；一個組合至少要選取一個數字。\(P = 10009\)，\(0 < n < 26\)。

例如輸入為 \(\{1, 1, 2\}\)，則有三種組合：選第一個 \(1\)，選第二個 \(1\)，以及選兩個 \(1\)。

輸入格式

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

限制

• \(P = 10009\)（固定）。
• \(1 \le n \le 25\)。
• \(1 \le A_i \le 10^9\)。

輸出格式

輸出有多少種組合。

評分說明

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

範例輸入 1

3
1 1 2

範例輸出 1

3

範例輸入 2

5
2 5005 10008 10008 3

範例輸出 2

3

範例說明

範例 2 中，\(2 \times 5005 = 10010\) 除以 \(10009\) 餘 \(1\)；\(10008 \times 10008\) 除以 \(10009\) 也餘 \(1\)；把這兩組合起來選四個數字，餘數仍是 \(1\)。共三種組合。

題目來源

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