Background

WAPER loves playing Hypixel (the world’s largest Minecraft minigame server) Build Battle!

Hint: In this problem, wool is considered a type of block.

Problem Description

Now WAPER is going to play $q$ rounds of Build Battle. At the beginning of the $i$-th round, WAPER chooses a parameter $m_i$, and places $n$ colored wool blocks in order. The color sequence is:

$$1,\ 2,\ ...\ ,\ m_i-1,\ m_i,\ 1,\ 2,\ ...\ ,m_i-1\ ,m_i\ ,\ ...\ (n-1) \ \bmod \ m_i+1$$

For example, when $n=7,m=3$, the color sequence is:

$$1\ ,2,\ 3,\ 1,\ 2,\ 3,\ 1$$

Now WAPER is going to break some blocks (he may break none, or break all). WAPER wants to know how many different color sequences can be produced this way. (Two color sequences are different if and only if their lengths are different, or the wool color at some position is different.)

Because the answer is too large, output the result modulo $10^9+7$.

(In fact, this asks for the number of essentially different subsequences of this sequence, modulo $10^9+7$.)

Input Format

The first line contains two integers $n$ and $q$, representing the number of wool blocks and the number of rounds.
The second line contains $q$ integers $m_i$, representing the parameters.

Output Format

Output $q$ lines, each containing one integer representing the answer.
Output the answer modulo $10^9+7$.

10 6
1 1 4 5 1 4

11
11
833
944
11
833

1000000 1
114514

945636198

Hint

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (5 pts): $n \le 20$, $q=1$.
• Subtask 2 (15 pts): $n \le 10^3$, $q=1$.
• Subtask 3 (15 pts): $\max\{m_i\} \le 20$, $q=1$.
• Subtask 4 (25 pts): $q=1$.
• Subtask 5 (40 pts): No special constraints.

For $100\%$ of the testdata, $1 \le n,q \le 10^6$, $1 \le m_i \le n$.

Additional Information

Minecraft OI Round 2 B

• Maker: WAPER420.
• Tester: 灵空 (Lingkong).

$The sample was not written by the problem setter!!!!!!!!!!!!!!!!!$

Translated by ChatGPT 5