ご存知の通り、六花は数学が苦手です。そこで勇太は彼女にゲームを教えることにしました。最初に整数 $x$ が与えられます。各数には「スコア」 $f(x)$ があり、以下の手順でゲームが進行します。

1. 自分のスコアに $f(x)$ を加算する。
2. もし $x = 1$ ならば、ゲーム終了。
3. そうでなければ、ランダムに素数 $p|x$ を選び、$x$ を $p$ で割る。その後、ステップ1に戻る。

スコアの期待値はいくらでしょうか？答えは $P = 10^9 + 7$ で割った余りを出力してください。

六花の計算能力を鍛えるため、勇太は彼女にできるだけ早く答えを出してほしいと考えています。また、問題が進むごとに勇太は $f$ の値を一つずつ変更します。もちろん、この問題は可愛い六花には難しすぎるため、あなたが彼女を助けてあげてください。

入力形式

1行目に2つの正整数 $x, t$ が与えられます。これは初期値と問題数（初期の $f$ も1問目とみなす）を表します。

続く1行には $d(x)$ 個の整数が与えられます（$d(x)$ は $x$ の約数の個数）。$i$ 番目の数は、$x$ の約数を小さい順に並べたときの $i$ 番目の数 $v$ に対するスコア $f(v)$ です。

続く $t - 1$ 行には、それぞれ2つの数 $v, y$ が与えられます。これは $f(v)$ を $y$ に変更することを意味します。$v|x$ であることが保証されており、変更は永続的です。

出力形式

$t$ 行出力してください。各行は、その時点での問題（初期の $f$、および $t-1$ 回の変更後の $f$）に対する答えを表します。

入出力例

入力 1

6 1
1 2 4 8

出力 1

12

注記

1回目、六花は 6 を 2 または 3 で割ることができます。しかし、次は必ず 1 になるため、等確率で2つの過程をたどります：6 → 3 → 1 または 6 → 2 → 1。それぞれの過程のスコアは 13 と 11 なので、期待値は 12 となります。

サブタスク

すべてのデータにおいて、$1\le x \le 10^{12}, 1\le t \le 3 \times 10^5, 1\le f(v), y \le 10^9$ を満たします。