Description

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...

Input Format

Since $n$ may be very large, we give the prime factorization of $n$.

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.)

Output Format

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

3 2 
2 1 
5 1

1100

Hint

Constraints

The information for each test point is shown in the table below.

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