輸入 $n$ 個正整數，請計算其中有多少組合的相乘積除以 $P$ 的餘數為 $1$，每個數字可以選取或不選取但不可重複選，輸入的數字可能重複。
$ P=10009 $
第一行是 $n$，$ 0<n<26 $
第二行是 $n$ 個以空白間隔的正整數 $a_i$，$a_i \leq 10^{4}$
有多少種組合。
若輸入為${1, 1, 2}$，則有三種組合，選第一個 $1$，選第二個 $1$，以及選兩個 $1$。
3 1 1 2
3