Nice Pairs (Hard Version)

Problem Description

You are given a sequence $a_1, a_2, \dots, a_n$ of $n$ positive integers and a positive integer $k$. Count how many pairs $(l, r)$ satisfy all of the following:

• $1 \le l < r \le n$;
• there exists an integer $x$ such that $a_l \times a_r = x^k$.

Input Format

The first line contains two integers $n, k$.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$.

Output Format

One integer: the number of valid pairs.

Sample Input

6 3
1 3 9 8 24 1

Sample Output

5

Constraints

For all test points, $2 \le n \le 10^6$, $2 \le k \le 100$, and $1 \le a_i \le 10^7$.