题目描述

Polycarp 非常喜欢等比数列，尤其喜欢长度为 $3$ 的等比数列。

他想知道对于一个给定长度 $n$ 的数列 $a$ 和公比 $q$，$a$ 中有多少个长度为 $3$ 的子序列是以 $q$ 为公比的等比数列。

$a_i,a_j,a_k$ 是一个公比为 $q$ 的等比数列是指 $a_k=q\times a_j$ 且 $a_j=q\times a_i$。

你要找出使得 $a_i,a_j,a_k$ 是一个公比为 $q$ 的等比数列的三元组 $(i,j,k)$ 的个数，且要保证 $1\le i<j<k\le n$。

输入描述

第一行两个整数 $n$（$1\le n\le 2\times10^5$）和 $q$（$-1\times10^3\le q\le 1\times10^3$，$q\ne 0$）。

第二行 $n$ 个整数表示 $a_i$（$-10^9\le a_i\le 10^9$，$a_i\ne 0$），$a_i$ 表示给定数列的第 $i$ 项。

输出描述

输出一个整数，表示 $a$ 中有多少个不同的以 $q$ 为公比，长度为 $3$ 的子序列。

样例 1

5 2
1 2 4 2 4

3

样例 2

3 1
1 1 1

1

样例 3

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

6

说明提示

样例 #1：$\{a_1,a_2,a_3\}$，$\{a_1,a_2,a_5\}$，$\{a_1,a_4,a_5\}$。

样例 #2：$\{a_1,a_2,a_3\}$。

样例 #3：$\{a_1,a_5,a_7\}$，$\{a_1,a_5,a_{10}\}$，$\{a_1,a_9,a_{10}\}$，$\{a_2,a_3,a_8\}$，$\{a_2,a_6,a_8\}$，$\{a_4,a_6,a_8\}$。

数据范围

$1\le n\le 2\times10^5$，$-10^3\le q\le 10^3$，$q\ne 0$。

$-10^9\le a_i\le 10^9$，$a_i\ne 0$。

录入校勘：原图“输入描述”里的非零符号显示不完整；以上按原图底部“数据范围”中明确的 $q\ne0$、$a_i\ne0$ 录入。