众所周知，六花的数学不太好，所以勇太开始教她玩一个游戏，一开始有一个整数，初始为 $x$。每个数都有一个“计分”我们记为 $f(x)$，接下来会执行这样一个过程：

1. 将自己的得分加上 $f(x)$
2. 如果 $x = 1$，结束游戏
3. 否则，随机选择一个素数 $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$