眾所周知，六花的數學不太好，所以勇太開始教她玩一個遊戲，一開始有一個整數，初始為 $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 \times 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$ |