P6271 [Hubei Provincial Team Mutual Test 2014] One Person's Number Theory

Source: Week 1 of the 2014 Hubei Provincial Team Mutual Test. Resource: [link](https://tieba.baidu.com/p/3050650090?red_tag=3002680446).

One day, hjy96 came up with a number theory problem: For a non-negative integer $d$ and a positive integer $n$, define $f_d(n)$ as the sum of the $d$-th powers of all positive integers less than $n$ and coprime to $n$. For example, $f_3(10) = 1^3 + 3^3 + 7^3 + 9^3$. Given $d$ and $n$, find the value of $f_d(n)$. Output the result modulo $10^9 + 7$. Of course, hjy96 knows how to do it. But he wants to challenge you...

Since $n$ may be very large, we give the prime factorization of $n$. $$ n=\prod_{i=1}^{w} p_{i}^{\alpha_{i}} $$ The first line contains a non-negative integer $d$ and a positive integer $w$, separated by spaces. The next $w$ lines each contain two positive integers $p_i$ and $\alpha_i$, separated by spaces. (It is guaranteed that each $p_i$ is prime and they are pairwise distinct.)

One line containing a non-negative integer, representing $f_d(n)$ modulo $10^9 + 7$.

#### Constraints The information for each test point is shown in the table below. | ID | $d$ | Special Constraints | | :---: | :---: | :---------: | | 1 | $\leq 100$ | $n \leq 10^5$ | | 2 | $=0$ | None | | 3 | $=1$ | None | | 4 | $=2$ | None | | 5 | $\leq 100$ | $w = 1$, $ \alpha_1 = 1$ | | 6 | $\leq 100$ | $w = 1$, $ \alpha_1 = 1$ | | 7 | $\leq 100$ | $ \prod_{i = 1}^w (\alpha_i + 1) \leq 10^5$ | | 8 | $\leq 100$ | $w \leq 16$ | | 9 | $\leq 100$ | None | | 10 | $\leq 100$ | None | For all test points, it is guaranteed that $1 \leq w \leq 10^3$, $2 \leq p_i \leq 10^9$, and $1 \leq \alpha_i \leq 10^9$. Translated by ChatGPT 5