1327 - Section of Zero

問題

整数 $M$ と長さ $N$ の整数列 $B = (b_1,b_2,\ldots,b_N)$ が与えられます。

$(1 \leq L \leq R \leq N)$ を満たす全ての $L,R$ の組のうち、$\displaystyle \prod_{k=L}^{R} b_k \bmod M = 0$ となるものの個数を求めてください。

ここで、$A \bmod B$ は $A$ を $B$ で割った余りを表します。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$
$b_1$ $b_2$ $\ldots$ $b_N$

出力

$(1 \leq L \leq R \leq N)$ を満たす全ての $L,R$ の組のうち、$\displaystyle \prod_{k=L}^{R} b_k \bmod M = 0$ となるものの個数を求めよ。
出力の末尾には改行を入れること。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 10^{10}$
• $1 \leq b_i \leq 10^{18}$ $(1 \leq i \leq N)$

入出力例

入力例１

3 5
6 5 2

出力例１

4

$(L=1,R=2)$ のとき、$(6 \times 5) \bmod 5 = 0$ となる。
$(L=1,R=3)$ のとき、$(6 \times 5 \times 2) \bmod 5 = 0$ となる。
$(L=2,R=2)$ のとき、$5 \bmod 5 = 0$ となる。
$(L=2,R=3)$ のとき、$(5 \times 2) \bmod 5 = 0$ となる。
条件を満たす $L,R$ の組はこの $4$ つのみである。

入力例２

5 13
9 8 2 4 2

出力例２

0

条件を満たす $L,R$ の組は存在しません。

入力例３

1 314
314

出力例３

1