As everyone knows, Rikka is not very good at mathematics, so Yuta starts teaching her a game. Initially, there is an integer $x$. Each number has a "score" denoted by $f(x)$. The process proceeds as follows:

1. Add $f(x)$ to the current score.
2. If $x = 1$, the game ends.
3. Otherwise, randomly choose a prime factor $p$ of $x$, and replace $x$ with $x/p$. Then return to step 1.

What is the expected total score? The answer should be modulo $P = 10^9 + 7$.

To train Rikka's calculation skills, Yuta wants her to answer his questions as quickly as possible. For each subsequent question, Yuta will modify the value of $f$ for a specific number. Of course, this problem is too difficult for the cute Rikka; can you help her?

Input

The first line contains two positive integers $x$ and $t$, representing the initial value and the number of questions (the initial $f$ values are also considered a question).

The next line contains $d(x)$ integers ($d(x)$ denotes the number of divisors of $x$), where the $i$-th number represents the score $f(v)$ for the $i$-th smallest divisor $v$ of $x$.

The next $t-1$ lines each contain two numbers $v$ and $y$, where $v|x$, indicating that $f(v)$ is updated to $y$. These modifications are cumulative (i.e., the changes are permanent).

Output

Output $t$ lines, representing the answer for each question (the initial $f$ values, and the state after each of the $t-1$ modifications).

Examples

Examples 1

6 1
1 2 4 8

Output 1

12

Note 1

In the first round, Rikka can divide 6 by 2 or 3, and in the next step, she will inevitably reach 1. Therefore, there are two equally probable processes: $6 \to 3 \to 1$ or $6 \to 2 \to 1$. The scores for these two processes are 13 and 11, respectively, so the expected value is 12.

Subtasks

For 100% of the data, $1\le x \le 10^{12}, 1\le t \le 3 \times 10^5, 1\le f(v),y \le 10^9$.