众所周知，六花的数学不太好，所以勇太开始教她玩一个游戏，一开始有一个整数，初始为 $x$。每个数都有一个“计分”我们记为 $f(x)$，接下来会执行这样一个过程：
- 将自己的得分加上 $f(x)$
- 如果 $x = 1$，结束游戏
- 否则，随机选择一个素数 $p|x$，将 $x$ 除以 $p$。然后回到第一步。
请问得分期望是多少？答案对 $P = 10^9 + 7$ 取模。
为了训练六花的计算能力，勇太希望六花能够尽快可能地回答他的问题，并且每次下一道题勇太都会修改某个 $f$ 的值。当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？
输入格式
第一行两个正整数 $x, t$，表示初始值和有多少道题（初始 $f$ 也视为一道题）。
接下来一行有 $d(x)$ 个数（ $d(x)$ 表示 $x$ 的因子数量），其中第 $i$ 个数表示 $x$ 的因数 中从小到大第 $i$ 个数 $v$ 的计分 $f(v)$。
接下来 $t − 1$ 行，每行两个数 $v, y$，保证 $v|x$，表示将 $f(v)$ 修改为 $y$，修改并不独立（即修改时永久的）。
输出格式
输出 $t$ 行，表示每道题（初始 $f$ 、以及 $t-1$ 次修改之后 $f$）对应的答案。
样例数据
样例 1 输入
6 1 1 2 4 8
样例 1 输出
12
样例 1 解释
第一次六花可以将 6 除以 2 或者 3，然而在下一次必然得到 1，因此等概率进行两 种过程：6 → 3 → 1 或者 6 → 2 → 1。两种过程的答案分别是 13 和 11，因此期望为 12。
子任务
对于 100% 的数据，$1\le x \le 10^{12}, 1\le t \le 3 × 10^5, 1\le f(v),y \le 10^9$
| 测试点 | $x$ | $t$ | $x$ 是某个素数的 $k$ 次幂 |
|---|---|---|---|
| $1 \sim 2$ | $\leq 20$ | $\leq 1$ | |
| $3 \sim 4$ | $\leq 10^9$ | ✓ | |
| $5 \sim 6$ | $\leq 10^6$ | ||
| $7 \sim 8$ | $\leq 10^3$ | ||
| $9$ | $\leq 10^{12}$ | ✓ | |
| $10$ | |||
| $11$ | $\leq 10^9$ | $\leq 5\,000$ | ✓ |
| $12$ | $\leq 10^{12}$ | $\leq 10^4$ | |
| $13$ | $\leq 10^9$ | $\leq 5 \times 10^4$ | |
| $14$ | $\leq 10^5$ | ||
| $15$ | $\leq 3\times 10^5$ | ||
| $16$ | ✓ | ||
| $17$ | $\leq 10^{12}$ | $\leq 10^4$ | |
| $18$ | $\leq 5 \times 10^4$ | ||
| $19$ | $\leq 10^5$ | ||
| $20$ | $\leq 3 \times 10^5$ |