This is the hard version of the problem. The only difference is that (1 \le x \le 5 \cdot 10^5) . On the way home after buying his favorite soda "Zola Cero", Egor saw that elections for the position of "Best Number" are taking place in Saransk. There are (n) people at the polling station. Each person brought a number (a_i). When the (i)-th person enters the voting booth, they choose a candidate that is a divisor of the number (a_i). Let the chosen candidate be (p_i). After everyone has voted, we get an array of votes (p_1, p_2, \ldots, p_n). Egor really likes the number (x) and considers the voting ideal if (x \cdot {lcm}(p_1, p_2, \ldots, p_n))(^{\text{∗}}) = (p_1 \cdot p_2 \cdot \ldots \cdot p_n). Help him find the number of different(^{\text{†}}) arrays (p) modulo (10^9 + 7) that are ideal. (^{\text{∗}})(lcm) — least common multiple . (^{\text{†}})Two arrays of votes are considered different if there exists an index (i) where the two arrays have different elements. The first line contains a single integer (t) ((1 \leq t \leq 10^4)) — the number of test cases. Then (t) test cases follow. The first line of each test case contains two integers (n) and (x) ((1 \leq n \leq 10^5), (1 \leq x \leq 5 \cdot 10^5)) — the number of voters at the polling station and Egor's favorite number. The second line of each test case contains (n) integers: (a_1, a_2, \dots, a_n) ((1 \leq a_i \leq 5 \cdot 10^5)) — the numbers brought by the voters. It is guaranteed that the sum of (n) over all test cases does not exceed (10^5). For each test case, output the number of ways modulo (10^9 + 7) to vote so that the resulting array of votes satisfies the condition.