Geometric Progression

Polycarp loves geometric progressions very much. Since he was only three years old, he loves only the progressions of length three. He also has a favorite integer k and a sequence a, consisting of n integers.He wants to know how many subsequences of length three can be selected from a, so that they form a geometric progression with common ratio k.A subsequence of length three is a combination of three such indexes i1, i2, i3, that 1 ≤ i1 < i2 < i3 ≤ n. That is, a subsequence of length three are such groups of three elements that are not necessarily consecutive in the sequence, but their indexes are strictly increasing.A geometric progression with common ratio k is a sequence of numbers of the form b·k0, b·k1, …, b·kr - 1.Polycarp is only three years old, so he can not calculate this number himself. Help him to do it.
Input
The first line of the input contains two integers, n and k (1 ≤ n, k ≤ 2·105), showing how many numbers Polycarp’s sequence has and his favorite number.The second line contains n integers a1, a2, …, an ( - 109 ≤ ai ≤ 109) — elements of the sequence.
Output
Output a single number — the number of ways to choose a subsequence of length three, such that it forms a geometric progression with a common ratio k.
Examples

Input
5 2
1 1 2 2 4
Output
4

Input
3 1
1 1 1
Output
1

Input
10 3
1 2 6 2 3 6 9 18 3 9
Output
6

#include <cstdio>
#include <cstring>
#include <map>
#include <iostream>
using namespace std;
typedef long long LL;

map<int, LL> s1, s2;
int main()
{
    LL n, k;
    LL ans, x;
    cin >> n >> k;
    ans = 0;
    for(int i = 0; i < n; i++)
    {
        scanf("%I64d",&x);
        if(x%k == 0)
        {
            LL t1 = s2[x/k];
            ans += t1;
            LL t2 = s1[x/k];
            s2[x] += t2;
        }
        s1[x]++;
    }
    cout << ans << endl;
    return 0;
}