About the Time Limit

Problem Statement

A positive integer $N$ is given.

There are towns numbered from $1$ to $N$, and PCT plays a game in which he aims to travel from town $1$ to town $N$. The number of towns he passes through, excluding town $1$ and town $N$, must be exactly $2$.

PCT keeps performing the following (Operation) until the game ends.

(Operation)

When PCT is in town $1$: He can move to any town other than town $1$.

When PCT is in a town other than town $1$ (let the current town be town $i$): He spins the gacha in that town. The gacha in town $i$ produces an integer between $1$ and $A_i$, inclusive. If a number other than $1$ comes out, he does not move to any town. If $1$ comes out, he can move to a town $j$ such that $j$, satisfying $i \neq j$, is a multiple of $i$. However, when there is no town to move to, the game ends.

In the end, the number of times PCT spun the gacha before the game ended was exactly $M$. Also, he was in town $N$ when the game ended.

Output the number of possible pairs of the sequence formed by arranging the numbers drawn from the gacha in order and the way of moving between towns, modulo $1000000007$.

Furthermore, $Q$ queries are added. Their content is as follows.

$Query: $ $X \ \ Y$ $(X < Y)$ : Makes it possible to move from town $X$ to town $Y$. This means that, while normally one can move to a town that is a multiple when the gacha shows $1$, one can now also move from town $X$ to town $Y$; it does not mean that one can move without the gacha showing $1$. It is guaranteed that, at the time the query is given, one cannot move directly from town $X$ to town $Y$. (At 21:56, $X \le Y$ was corrected to $X < Y$.)

Here, being unable to move from town $X$ to town $Y$ means that $Y$ is not a multiple of $X$ and that the same $(X,Y)$ has not appeared in any previous query.

Each time a query is added, output the number of possible pairs of the sequence formed by arranging the numbers drawn from the gacha in order and the way of moving between towns, modulo $1000000007$.

(Note) Regarding "pairs of the sequence formed by arranging the numbers drawn from the gacha in order and the way of moving between towns", two pairs are considered different if the number drawn on the $i (1 \leqq i \leqq M)$-th gacha spin differs, or if the 1st or 2nd town passed through differs.

Input

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

$X$ $Y$

• All input values are integers.
• $2 \le N \le 10^6$
• $3 \le M \le 10^6$
• $2 \le A_i \le 10^6$
• If $i \neq j $, then $A_i \neq A_j$
• $0 \le Q \le 10^4$
• $2 \le X < Y \le N$
• When each query is given, one cannot move directly from town $X$ to town $Y$.

Output

The output consists of $Q+1$ lines. On line $i$, output the answer for the situation in which the queries up to the $i-1$-th have been added. Here, the $0$-th refers to the situation in which no queries have been added.

Sample

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