制限実行時間について

問題文

ある正整数 $N$ が与えられます。

$1$ から $N$ の番号がついた町があり、PCT君は町 $1$ から 町 $N$ を目指すゲームを行います。 経由する街の数は、町 $1$ と町 $N$ を除いてちょうど $2$ 個になるようにします。

PCT君は、以下の (操作) をゲームが終了するまで行い続けます。

(操作)

PCT君が町 $1$ にいる時 : 町 $1$ 以外の任意の町に移動できます。

PCT君が町 $1$ 以外にいる時 (現在いる町を町 $i$ とします) : その町にあるガチャを回します。 町 $i$ にあるガチャは $1$ 以上 $A_i$ 以下の整数が出てきます。 この時、$1$ 以外の数が出てきた場合はどこの町へも移動しません。 また、$1$ が出てきた場合は、$i \neq j$ を満たす $j$ が $i$ の倍数である町 $j$ へと移動することができます。 ただし、移動する町が無くなったときは、このゲームを終了します。

最終的に、PCT君がゲームが終了するまでに回したガチャの回数はちょうど $M$ 回でした。また、ゲームが終了した時町 $N$ にいました。

この時、考えられうるガチャで出た数字を順番に並べて出来る数列と町の移動の仕方の組としてあり得るものの個数を $1000000007$ で割った余りを出力してください。

またさらに、クエリを $Q$ 個追加します。内容は以下の通りです。

$Query: $ $X \ \ Y$ $(X < Y)$ : 町 $X$ から町 $Y$ へ移動可能にします。この移動可能とはガチャで $1$ が出た時に本来倍数の町に移動が可能ですが、町 $X$ から町 $Y$ も移動可能にするということであり、ガチャで $1$ が出なくても移動できるというわけではありません。ただし、クエリが与えられた段階では町 $X$ から町 $Y$ に直接移動することは出来ないことが保証されます。(21:56 $X \le Y$ を $X < Y$ に修正しました。)

ここで町 $X$ から町 $Y$ へ移動が出来ないということは $Y$ が $X$ の倍数でなく、かつ今までのクエリに同一の $(X,Y)$ がないということです。

クエリが追加される度に、考えられうるガチャで出た数字を順番に並べて出来る数列と町の移動の仕方の組としてあり得るものの個数を $1000000007$ で割った余りを出力してください。

(補足) 「考えられうるガチャで出た数字を順番に並べて出来る数列と町の移動の仕方の組」は、$i (1 \leqq i \leqq M)$ 回目のガチャで出た数字が異なる時、また、1個目または2個目の経由する町が異なる時、別の組として考えます。

入力

$N$ $M$
$A_2\ A_3\ \dots\ A_N$
$Q$
$Query1$
$Query2$
...
$QueryQ$

$X$ $Y$

• 入力は全て整数である。
• $2 \le N \le 10^6$
• $3 \le M \le 10^6$
• $2 \le A_i \le 10^6$
• $i \neq j $であれば$A_i \neq A_j$
• $0 \le Q \le 10^4$
• $2 \le X < Y \le N$
• 各クエリが与えられたとき町 $X$ から町 $Y$ へは直接移動出来ない。

出力

出力は $Q+1$ 行に渡ります。$i$ 行目には $i-1$ 個目までのクエリが追加された状況での答えを出力してください。ただし $0$ 個目とはクエリが追加されていない状況のことを指します。

サンプル

8 4
2 3 4 5 6 7 8
2
3 8
2 3

11
11
21

5 4
10 100 1000 10000
0

0

8 1000000
2 3 4 5 6 7 8
0

26342024