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

輸入格式

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

輸出格式

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

範例輸入

3
1 1 2

範例輸出

3