問題文

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

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

部分列とは

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

制約

• $2 \leq N \leq 2 \times 10^5$
• $2 \leq K \leq N$
• $1 \leq M, A_i \leq 2 \times 10^5$
• 入力はすべて整数

入力

出力

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

サンプル

5 4 3
8 3 80 4 164

4

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

• $[8,80,4]$
• $[8,80,164]$
• $[8,4,164]$
• $[80,4,164]$

5 6 3
12 12 12 12 6

6