题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$，以及一个整数 $t$。

请你找出数列 $a$ 中存在多少个长度恰好为 $3$ 的子序列，并且这个子序列是一个公比为 $t$ 的等比数列。

换句话说，你需要找到存在多少个三元组 $(i, j, k)$ 满足：

$1 \le i \lt j \lt k \le n$ 且 $a_i \times t = a_j$ 且 $a_j \times t = a_k$.

输入格式

第一行，两个整数 $n$ 和 $k$，以一个空格分隔。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，相邻整数间以一个空格分隔。

输出格式

输出一个整数，表示数列 $a$ 中存在多少个长度为 $3$ 的子序列是公比为 $k$ 的等比数列。

5 2
1 1 2 2 4

4

3 1
1 1 1

1

10 3
1 2 6 2 3 6 9 18 3 9

6

说明/提示

样例解释

以下都用 $(i, j, k)$ 的格式表示 $a_i, a_j, a_k$ 构成一个满足条件的子序列。

样例1：$(1,3,5)$，$(1,4,5)$，$(2,3,5)$，$(2,4,5)$

样例2：$(1,2,3)$

样例3：$(1,5,7)$，$(1,5,10)$，$(1,9,10)$，$(2,3,8)$，$(2,6,8)$，$(4,6,8)$

数据规模与约定

• 对于 $30\%$ 的数据，$n,k \le 20; a_i \le 1000$；
• 对于 $60\%$ 的数据，$n,k \le 2000; a_i \le 10^6$；
• 对于 $100\%$ 的数据，$1 \le n,k \le 2 \cdot 10^5; 1 \le a_i \le 10^9$。