406060: GYM102253 E Expectation of Division

To be frank with you, this problem is an extension of a classic problem, of which the colossal data range might increase its difficulty.

Let's define a type of operation with respect to a positive integer $$$n$$$ as replacing it with one of its positive factor $$$d$$$.

Given the integer $$$n$$$ ($$$n > 1$$$), you are asked to determine the expected times of doing this operation repeatedly until $$$n$$$ is changed into $$$1$$$ for the first time, assuming that $$$d$$$ is selected with equal probability among all the possible factors at any time.

For ease of calculation, $$$n$$$ and all its distinct prime factors $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_m$$$ will be given.

To avoid the precision issue, let's express the expected value as a reduced fraction $$$\frac{a}{b}$$$, and you should output the minimum non-negative integer $$$c$$$ such that $$$b c \equiv a \pmod{10^9 + 7}$$$.

The input contains multiple (about $$$2 \times 10^5$$$) test cases.

For each test case, the first line contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 10^{24}$$$, $$$m \geq 1$$$), where $$$m$$$ indicates the number of distinct prime factors of $$$n$$$.

The second lines contains $$$m$$$ distinct prime numbers $$$p_1, p_2, \ldots, p_m$$$ ($$$2 \leq p_1, p_2, \ldots, p_m \leq 10^6$$$).

For each test case, output "Case #x: y" in one line (without quotes), where $$$x$$$ indicates the case number starting from $$$1$$$, and $$$y$$$ denotes the answer to the corresponding case.

It is guaranteed that the answer exists for each test case.

2 1
2
4 1
2
6 2
2 3
8 1
2
10 2
2 5
12 2
2 3

Case #1: 2
Case #2: 500000006
Case #3: 666666674
Case #4: 833333342
Case #5: 666666674
Case #6: 233333338