問題文
長さNの数列Aが与えられます.数列Aの長さKの部分列で,全要素の最大公約数がMとなるものの個数を1000000007で割ったあまりを求めてください.
ただし,部分列の要素が同じでも、取り出す位置が異なっていれば別の部分列として数えます.
部分列とは
数列Aの部分列とは,Aから0個以上の要素を取り除いた後,残りの数字を元の順序で並べて得られる数列のことです.
制約
- 2≤N≤2×105
- 2≤K≤N
- 1≤M,Ai≤2×105
- 入力はすべて整数
入力
出力
数列Aの長さKの部分列で,全要素の最大公約数がMとなるものの個数を求めてください.
サンプル
長さ3の部分列のうち,全要素の最大公約数が4となるものは以下の4つです.
- [8,80,4]
- [8,80,164]
- [8,4,164]
- [80,4,164]