問題文

長さ N の整数列 A = (A_1, A_2, \dots, A_N) と整数 M が与えられます。
以下の条件をすべて満たす整数の組 (i,j,k) の個数を求めてください。

• 1\leq i,j,k \leq N
• i, j, k は全て異なる
• A_i \times M^{A_j}=A_k

制約

• 3\leq N\leq 2\times10^5
• 1\leq M\leq 10^{18}
• 0\leq A_i\leq10^{18}
• 入力はすべて整数

入力例 1

5 2
1 2 4 8 16

出力例 1

6

条件を満たす (i, j, k) の組合せは以下の 6 通りです。

• (1, 2, 3)
• (1, 3, 5)
• (2, 1, 3)
• (3, 1, 4)
• (3, 2, 5)
• (4, 1, 5)

入力例 2

8 3
0 3 2 6 18 1 2 0

出力例 2

21

入力例 3

12 1
0 0 0 0 0 0 0 1 1 1 1 1

出力例 3

620