問題文

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

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

部分列とは

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

制約

  • 2N2×1052 \leq N \leq 2 \times 10^5
  • 2KN2 \leq K \leq N
  • 1M,Ai2×1051 \leq M, A_i \leq 2 \times 10^5
  • 入力はすべて整数

入力

N M KN\ M\ K
A1ANA_1 \dots A_N

出力

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

サンプル

入力例1
5 4 3
8 3 80 4 164
出力例1
4

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

  • [8,80,4][8,80,4]
  • [8,80,164][8,80,164]
  • [8,4,164][8,4,164]
  • [80,4,164][80,4,164]
入力例2
5 6 3
12 12 12 12 6
出力例2
6

Submit


Go (1.21)