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 i_1, i_2, i_3, that 1 ≤ i_1 < i_2 < i_3 ≤ 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·k^0, b·k^1, ..., b·k^{r} - 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·10^5), showing how many numbers Polycarp's sequence has and his favorite number.

The second line contains n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — 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


-----Note-----

In the first sample test the answer is four, as any of the two 1s can be chosen as the first element, the second element can be any of the 2s, and the third element of the subsequence must be equal to 4.

Difficulty: interview

Starter code:

Solutions:
def main():
    import sys
    from collections import defaultdict
    
    tokens = [int(i) for i in sys.stdin.read().split()]
    tokens.reverse()
    
    n, k = tokens.pop(), tokens.pop()
    
    d1 = defaultdict(int)
    d2 = defaultdict(int)
    result = 0
    for i in tokens:
        result += d2[i * k]
        d2[i] += d1[i * k]
        d1[i] += 1
    
    print(result)
    
    
main()


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

d = { }
d2 = { }
result = 0

for x in a:
    cur = d2.get(x)
    if cur is not None:
        result += cur
    cur = d.get(x)
    if cur is not None:
        d2[k * x] = d2.get(k * x, 0) + cur
    d[k * x] = d.get(k * x, 0) + 1

print(result)


n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
z = dict()
s = 0
for i in range(n):
    if not a[i] in z:
        z[a[i]] = [0, 0, 0]
    if a[i] % (k * k) == 0 and a[i] // k in z:
        q = z[a[i] // k][1]
        z[a[i]][2] += z[a[i] // k][1]
        s += q
    if a[i] % k == 0 and a[i] // k in z:
        z[a[i]][1] += z[a[i] // k][0]
    z[a[i]][0] += 1
print(s)


n, k = [int(i) for i in input().split()]
s = [int(i) for i in input().split()]
ans = 0
c = {}
c2 = {}
for i in s:
    if i in c:
        c[i]+=1
    else:
        c[i] = 1
    if i%(k) == 0:
        if i in c2:
            if i//k in c:
                c2[i]+=c[i//k]
        else:
            if i//k in c:
                c2[i]=c[i//k]
            else:
                c2[i]= 0
    if i%(k*k) == 0:
        if i//(k*k) == i//(k):
            ans+=(c[i//(k*k)]-1)*(c[i//(k*k)]-2)//2
        else:
            if i//k in c2:
                ans+=c2[i//k]
print(ans)


def get_sequence(a_indices, b_indices, c_indices):
    a_i, b_i, c_i = 0, 0, 0
    i = 0
    total = len(a_indices) + len(b_indices) + len(c_indices)
    a_indices = a_indices[:]
    b_indices = b_indices[:]
    c_indices = c_indices[:]

    a_indices.append(1000005001)
    b_indices.append(1000005001)
    c_indices.append(1000005001)
    sequence = []
    while i < total:
        minimum = calculate_minimum(a_indices[a_i], b_indices[b_i], c_indices[c_i])
        if minimum == 'a':
            a_i += 1
        elif minimum == 'b':
            b_i += 1
        elif minimum == 'c':
            c_i += 1
        sequence.append(minimum)
        i += 1

    return sequence


def calculate(a_indices, b_indices, c_indices):
    sequence = get_sequence(a_indices, b_indices, c_indices)

    a_stack, b_stack, c_stack = 0, 0, 0

    for ch in sequence:
        if ch == 'a':
            a_stack += 1
        elif ch == 'b':
            b_stack += a_stack
        elif ch == 'c':
            c_stack += b_stack

    return c_stack


def calculate_minimum(a_index, b_index, c_index):
    if a_index < b_index:
        if a_index < c_index:
            return 'a'
        else:
            return 'c'
    else:
        if b_index < c_index:
            return 'b'
        else:
            return 'c'


def main():
    n, k = [int(t) for t in input().split()]
    a_list = [int(t) for t in input().split()]
    hash_map = {}
    for index, a in enumerate(a_list):
        if a in hash_map:
            hash_map[a].append(index)
        else:
            hash_map[a] = [index]

    total_gp = 0
    if k != 1:
        for a1 in list(hash_map.keys()):
            a2 = a1 * k
            a3 = a2 * k
            if a2 in hash_map and a3 in hash_map:
                total_gp += calculate(hash_map[a1], hash_map[a2], hash_map[a3])
    else:
        for a in list(hash_map.keys()):
            count = len(hash_map[a])
            if count >= 3:
                nc3 = count * (count - 1) / 2 * (count - 2) / 3
                total_gp += int(nc3)

    print(total_gp)


def __starting_point():
    main()

__starting_point()

n, k = list(map(int, input().split(" ")))
a = input().split(" ")
arr = {}
zeroes = 0
lst = {}
ans = 0
for i in a:
    i = int(i)
    if i == 0:
        zeroes += 1
    else:
        if i in list(arr.keys()):
            arr[i][0] +=1
            if (i % k == 0) and (i//k in list(lst.keys())):
                arr[i][1] += arr[i//k][0] 
        else:
            arr[i] = [1, 0]
            if (i % k == 0) and (i//k in list(lst.keys())):
                arr[i][1] = arr[i//k][0] 
            lst[i] = True
            
        if (i % k == 0) and (i//k in list(lst.keys())) :
            ans += arr[i//k][1]
            #print (ans)

if k == 1:
    ans = 0
    for i in lst:
        ans += arr[i][0]*(arr[i][0]-1)*(arr[i][0]-2)//6

ans += zeroes * (zeroes-1) * (zeroes-2) //6
        
    
print (ans)


import collections
import bisect

def solve1(dp):
    count = 0
    for num in dp.values():
        n = len(num)
        if n >= 3:
            count += n * (n - 1) * (n - 2) // 6
    return count

def solve(n, k, As, dp):
    count = 0
    for i, ak in enumerate(As):
        if ak % k:
            continue
        if ak == 0:
            continue
        a = ak // k
        akk = ak * k
        n_left = bisect.bisect_left(dp[a], i)
        n_right = len(dp[akk]) - bisect.bisect_left(dp[akk], i)
        count += n_left * n_right
    n0 = len(dp[0])
    if n0 >= 3:
        count += n0 * (n0 - 1) * (n0 - 2) // 6
    return count

n, k = map(int, input().split())
As = list(map(int, input().split()))
dp = collections.defaultdict(list)
for i, a in enumerate(As):
    dp[a].append(i)

if n < 3:
    print(0)
elif k == 1:
    print(solve1(dp))
else:
    print(solve(n, k, As, dp))

n, k = [int(x) for x in input().split()]
mas = [int(x) for x in input().split()]
dictyCount = {}
dictyAns = {}
ans = 0

for x in mas[::-1]:
	ans += dictyAns.get(x * k, 0)
	
	dictyAns[x] = dictyAns.get(x, 0) \
					+ dictyCount.get(x * k, 0)
	dictyCount[x] = dictyCount.get(x, 0) + 1

print(ans)

s=0
m={}
o={}
n,k=map(int,input().split())
l=list(map(int,input().split()))
for a in l: o[a/k]=m[a/k]=m[a]=o[a]=0
for a in l:
 if a%k==0:
  s+=m[a/k]
  m[a]+=o[a/k]
 o[a]+=1
print(s)

d = {}
data = input().split()
k = int(data[1])
data = input().split()
ans = 0
for el in data:
	v = int(el)
	p = [0,0,]

	if v in list(d.keys()):
		p = d[v]

	

	if v%k==0 and (v/k) in list(d.keys()):
		ans += d[v/k][1]
		p[1] += d[v/k][0]
		

	p[0] += 1
	d[v] = p

print(ans)




s=0
m={}
o={}
n,k=map(int,input().split())
l=list(map(int,input().split()))
for a in l:
 if a%k==0:
  s+=m.get(a/k,0)
  m[a]=m.get(a,0)+o.get(a/k,0)
 o[a]=o.get(a,0)+1
print(s)

from sys import stdin, stdout
from collections import defaultdict

n,k = [int(x) for x in stdin.readline().rstrip().split()]
nums = [int(x) for x in stdin.readline().rstrip().split()]

a=defaultdict(lambda: 0)
b=defaultdict(lambda: 0)

ans = 0

for i in range(n):
    num = nums[i]
    if num % k == 0:
        ans += b[int(num/k)]
        b[num] += a[int(num/k)]
    a[num]+=1
print(ans)

from collections import defaultdict
import time

def __starting_point():

    n , k = [int(x) for x in input().split()]
    nums = [int(x) for x in input().split()]

    #n , k = 200000 , 1
    #nums = [1 for i in range(n)]

    #t1 = time.time()

    left = [0]*len(nums)
    predict = defaultdict( int )
    for i in range( len(nums) ):
        num = nums[i]
        if num%k == 0:
            left[i] = predict[num//k]
        predict[num] += 1
        #print( i , ":" , predict )

    right = [0]*len(nums)
    nextdict = defaultdict( int )
    for i in range( len(nums) - 1 , -1 , -1 ):
        num = nums[i]
        right[i] = nextdict[num*k]
        nextdict[num] += 1
    #print( "left :" , left )
    #print( "right :" , right )
    print( sum([left[i]*right[i] for i in range(len(nums))]) )

    #t2 = time.time()
    #print( t2-t1 , "s" )
        
            
                    

__starting_point()

n,k = map(int,input().split())
nums = [int(x) for x in input().split()]
zero = {}
one = {}
ans = 0
for i in range(n):
    x = nums[i]
    if x%k==0:
        if x//k in one:
            ans+=one[x//k]
        if x//k in zero:
            if x not in one:
                one[x] = 0
            one[x]+=zero[x//k]
    if x not in zero:
        zero[x] = 0
    zero[x]+=1
print(ans)

s=0
m={}
o={}
n,k=map(int,input().split())
l=list(map(int,input().split()))
for a in l:
 if a%k==0:
  s+=m.get(a/k,0)
  m[a]=m.get(a,0)+o.get(a/k,0)
 o[a]=o.get(a,0)+1
print(s)

inp, inp1 = map(int, input().split())
inp2 = list(map(int, input().split()))

dictionary = {}
dictionaryFNums = {}

k = inp1
res = 0
for n in range(inp):
    element = inp2[n]
    if (element % k == 0):
        res += dictionary.get(element/k, 0)
        dictionary[element] = dictionary.get(element, 0) + dictionaryFNums.get(element/k, 0)
    dictionaryFNums[element] = dictionaryFNums.get(element, 0)+1
print(res)

import collections
k=int(input().split()[1])
d=[collections.defaultdict(int)for _ in"123"]
for x in map(int,input().split()):
	d[2][k*x]+=d[1][x]
	d[1][k*x]+=d[0][x]
	d[0][k*x]+=1
print(sum(d[2].values()))


n, k = list(map(int,input().split()))
main = list(map(int,input().split()))

freq, kolgeom, kolvo = {},{},0

for a in main:
    if not (a in freq): freq[a]=0
    if a % k == 0:
        if (a / k) in kolgeom: kolvo += kolgeom[a / k]
        if not(a in kolgeom): kolgeom[a] = 0
        if (a / k) in freq: kolgeom[a] += freq[a / k]
    freq[a]+=1
print(kolvo)



import sys
from collections import defaultdict

#sys.stdin = open('input')


def main():
    n, k = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    current_sequence = defaultdict(list)
    total_subsequences = 0
    default = [0, 0]
    for elem in a:
        previous = elem / k
        if elem not in current_sequence:
            current_sequence[elem] = default.copy()
        total_subsequences += current_sequence.get(previous, default)[0]
        current_sequence[elem][0] += current_sequence.get(previous, default)[1]
        current_sequence[elem][1] += 1
    print(total_subsequences)

main()


from collections import defaultdict
import functools


def main():
    N, K = tuple(int(n) for n in input().split())
    NS = tuple(int(n) for n in input().split())
    nst = defaultdict(lambda: [0, 0, 0])

    for n in NS:
        if n == 0:
            nst[0][2] += nst[0][1]
            nst[0][1] += nst[0][0]
            nst[0][0] += 1
        else:
            d, m = divmod(n, K)
            if d != 0 and m == 0:
                nst[n][2] += nst[n//K][1]
                nst[n][1] += nst[n//K][0]
            nst[n][0] += 1
    print(functools.reduce(lambda x, y: x + y[2], nst.values(), 0))


def __starting_point():
    main()
__starting_point()

n,k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
lf = {}
rt = {}
for x in a:
    lf[x] = 0
    try:
        rt[x] += 1
    except KeyError:
        rt[x] = 1

prog = 0
for x in a:
    try:
        if(x%k==0):
            rt[x] -= 1
            prog += lf[x//k]*rt[x*k]
    except KeyError:
        pass
    finally:
        
        lf[x] += 1


print(prog)
    


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

d1 = {a[0] : 1}
d2 = {}
dp1 = [0]
dp2 = [0, 0]
for i in range(1, n):
    if a[i] % k == 0 and a[i] // k in d1:
            dp1.append(d1[a[i] // k])
            if a[i] % (k ** 2) == 0 and a[i] // k in d2:
                #dp2.append(sum(d2[a[i] // k]))
                dp2.append(d2[a[i] // k])
            else:
                dp2.append(0)
    else:
        dp1.append(0)
        dp2.append(0)
    if a[i] in d1:
        d1[a[i]] += 1
    else:
        d1[a[i]] = 1
    if a[i] in d2:
        d2[a[i]] += dp1[i]
    else:
        d2[a[i]] = dp1[i]

print(sum(dp2))


from collections import Counter

n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]


lk = {}
ans = 0

rk = Counter(a)

for x in a:
    rk[x] -= 1
    if x%k == 0:
        ans += lk.get(x/k, 0) * rk.get(x*k, 0)
    lk[x] = 1 + lk.get(x, 0)

print(ans)


n,k= list(map(int,input().split(" ")))
mas=list(map(int,input().split(" ")))
di=dict()
res=9999999999999999999999999999999999999
for i in mas:
    a = i*k
    a3 = str(a)+"_3"
    a2=str(a)+"_2"
    s1 = str(i)+"_1"
    s2=str(i)+"_2"
    s3=str(i)+"_3"
    if di.get(s3):
        res+=di.get(s3)
    if di.get(s2):
        if di.get(a3):
            di[a3]+=di.get(s2)
        else:
            di[a3]=di.get(s2)
    if di.get(s1):
        if di.get(a2):
            di[a2]+=1
        else:
            di[a2]=1
        di[s1]+=1
    else:
        if di.get(a2):
            di[a2]+=1
        else:
            di[a2]=1
        di[s1]=1


print(res-9999999999999999999999999999999999999)




__author__ = 'taras-sereda'

from collections import Counter

n,k = list(map(int,input().split()))
sequence = list(map(int,input().split()))
r = Counter(sequence)
l = dict.fromkeys(r,0)
# print(sequence)
# print(r)
res = 0
for i in sequence:
    r[i] -= 1
    if i%k == 0 and int(i*k) in r and int(i/k) in l:

        res += r[i*k] * l[i/k]
    l[i] += 1

print(res)