G. Danna and the Cheater
time limit per test
0.4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Danna is organizing a downhill tournament called "The Montes Tournament" on a peculiar mountain.

The mountain consists of $$$N - 1$$$ checkpoints, numbered from $$$2$$$ to $$$N$$$. Each checkpoint is connected by directed paths following a strict rule:

For each checkpoint $$$v$$$, there exists a directed edge $$$v → u$$$ if and only if $$$u$$$ divides $$$v$$$.

Note that the checkpoint with value $$$1$$$ does not exist.

A player starts at a checkpoint $$$x$$$ and wins if they manage to reach a target checkpoint $$$y$$$. However, Danna knows that one of the players is a cheater.

Although the cheater can bend the rules, they have a serious weakness.

The cheater has never seen any checkpoint higher than their starting position $$$x$$$. The thought of climbing to an unknown height terrifies them.

Because of this fear, the cheater will never move to any checkpoint $$$z$$$ such that $$$z \gt x$$$, under any circumstances.

This restriction applies even when cheating.

The cheater may perform at most one cheating move during the entire run.

A cheating move allows the player to take an edge that is originally directed into their current checkpoint and move to its origin.

Example:

There exists a directed edge $$$4 \rightarrow 2$$$. If the player is currently at checkpoint $$$2$$$, they may cheat to move to checkpoint $$$4$$$.

Once the cheating move is used, the cheater stop moving.

You are given $$$Q$$$ independent queries.

For each query, you are given a starting checkpoint $$$x$$$. A target checkpoint $$$y$$$ is chosen uniformly at random from all integers such that: $$$2 \leq y \leq N$$$.

Your task is to compute the probability that the cheater cannot reach $$$y$$$ starting from $$$x$$$, using directed edges and at most one cheating move.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ $$$(2 \leq N \leq 10^7, 1 \leq Q \leq 2*10^5)$$$.

The following $$$Q$$$ lines each contain a single integer $$$x_i$$$ $$$(2 \leq x_i \leq N)$$$, representing the starting checkpoint for the $$$i$$$-th query.

Output

For each query, output a single integer representing the probability that a randomly chosen target checkpoint $$$y$$$ the cheater starting at checkpoint $$$x_i$$$ can not win.

The probability must be expressed as an irreducible fraction $$$\frac{P}{Q}$$$. Print the value of $$$P \cdot Q^{-1}$$$ modulo $$$10^9 + 7$$$, where $$$Q^{-1}$$$ denotes the modular multiplicative inverse of $$$Q$$$ modulo $$$10^9 + 7$$$.

Examples
Input
8 1
4
Output
714285720
Input
6 1
6
Output
400000003
Note

In the first case, we observe that checkpoint $$$4$$$ has a directed edge to checkpoint $$$2$$$. By using a cheating move, it is possible to traverse edges in reverse, which would normally allow reaching checkpoints $$$2$$$, $$$4$$$, $$$6$$$, and $$$8$$$.

However, since the cheater is afraid of visiting checkpoints higher than the original starting point, they are restricted to checkpoints $$$z \le x$$$. Therefore, only checkpoints $$$2$$$ and $$$4$$$ are reachable.

If the cheating move is used at checkpoint $$$4$$$, the player can only return to the same checkpoint. Thus, out of the $$$7$$$ possible checkpoints, only $$$2$$$ are reachable and $$$5$$$ are not.

Hence, the answer is: $$$$$$\frac{5}{7} \equiv 714285720$$$$$$

In the second case, the player can reach only checkpoints $$$\{2, 3, 4, 6\}$$$. This means that exactly $$$1$$$ out of the $$$5$$$ checkpoints is unreachable.

Therefore, the answer is: $$$$$$\frac{1}{5} \equiv 400000003$$$$$$