P6811 “MCOI-02” Build Battle: Master Builder

WAPER loves playing Hypixel (the world’s largest Minecraft minigame server) Build Battle! Hint: In this problem, wool is considered a type of block.

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$.)

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 $q$ lines, each containing one integer representing the answer. Output the answer modulo $10^9+7$.

#### 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