Problem Description

Young Alisa enjoys playing the piano with just one finger. However, since Alisa has never learned how to play the piano, her playing process is entirely random. More precisely, she will equally likely choose any of the $N$ tones on the piano, and this choice is independent of all previous selections.

Alisa's friend Mirta wants to listen to a continuous sequence of $M$ tones $A_1, A_2, \dots, A_M$. However, due to Alisa's completely random playing, Mirta is only interested in knowing, for all $1 \leqslant i \leqslant M$, the expected number of times Alisa needs to choose a tone for Mirta to hear the continuous sequence $A_1, A_2, \dots, A_i$ for the first time. To prevent precision loss, the answer should be taken modulo $\bf 10^9+7$.

Input Format

The first line contains an integer $N$, representing the number of tones.
The second line contains an integer $M$, representing the number of tones in the sequence Mirta wants to hear.
The following $M$ lines each contain an integer $A_i$, representing the $i$-th tone in the sequence.

Output Format

Output $M$ lines, each containing a positive integer. The $i$-th line represents the expected number of times Alisa needs to choose a tone for Mirta to hear the continuous sequence $A_1, A_2, \dots, A_i$ for the first time, modulo $\bf 10^9+7$.

Sample Input and Output

Sample Input #1

2
2
1
2

Sample Output #1

2
4

Sample Input #2

2
2
1
1

Sample Output #2

2
6

Sample Input #3

3
3
1
2
3

Sample Output #3

3
9
27

Notes

[Data Range]

For $40\%$ of the data, it is guaranteed that $1 \leqslant M \leqslant 200$.
For all data, $1 \leqslant N \leqslant 100$, $1 \leqslant M \leqslant 10^6$, $1 \leqslant A_i \leqslant N$.

[Problem Source]

This problem is from COCI 2016-2017 CONTEST 7 T6 KLAVIR, configured according to the original problem data, with a full score of $160$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分