問題文

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

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

また，数列の要素が$1$つの場合はその要素の値を最大公約数とします．つまり，任意の自然数$x$について，$\gcd(x) = x$です．

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, M \leq 10^{18} \quad (1 \leq i \leq N)$
• 入力はすべて整数

入力

出力

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

サンプル

5 10
12 48 24 30 20

1

数列$A$の空でない連続部分列で，全要素の最大公約数が$10$となるものは以下の$1$つのみです．

• $[30, 20]$

5 6
12 48 24 30 20

3

数列$A$の空でない連続部分列で，全要素の最大公約数が$6$となるものは以下の$3$つです．

• $[12, 48, 24, 30]$
• $[48, 24, 30]$
• $[24, 30]$