CF2236F2 Elections in Saransk (hard version)

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](https://codeforces.com/r/lcm-wiki). $ ^{\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.