Cho một dãy gồm ~n~ số nguyên dương ~a_1, a_2, a_3, \ldots, a_n~ và một số nguyên dương ~m~. Hãy đếm số bộ ba ~(i, j, k)~ thoả mãn: ~1 \leq i < j < k \leq n~ và dãy ~[a_i, a_j, a_k]~ tạo thành một cấp số nhân công bội ~m~ (hay nói cách khác, ~a_i = b \times m^0, a_j = b \times m^1, a_k = b \times m^2~ với một số nguyên ~b~ nào đó).

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ và ~m~ (~3 \leq n, m \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, a_3, \ldots, a_n~ (~|a_i| \leq 10^9~).

Output

In ra số lượng bộ ba ~(i, j, k)~ thoả mãn.

Subtasks

• Subtask 1 (~20\%~): ~n \leq 200~.
• Subtask 2 (~20\%~): ~n \leq 10^3~.
• Subtask 3 (~60\%~): Không có điều kiện gì thêm.

Sample Test 1

Input:

5 2
1 1 2 2 4

Output:

4

Sample Test 2

Input:

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

Output:

6