GCD of Subsequence

長さの数列が与えられます．数列の長さの部分列で，全要素の最大公約数がとなるものの個数をで割ったあまりを求めてください．

ただし，部分列の要素が同じでも、取り出す位置が異なっていれば別の部分列として数えます．

数列の部分列とは，から個以上の要素を取り除いた後，残りの数字を元の順序で並べて得られる数列のことです．

• 入力はすべて整数

数列の長さの部分列で，全要素の最大公約数がとなるものの個数を求めてください．

5 4 3
8 3 80 4 164

4

長さの部分列のうち，全要素の最大公約数がとなるものは以下のつです．

5 6 3
12 12 12 12 6

6