問題
整数 $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