Problem Description

Young Alisa likes to play the piano using only one finger. However, since Alisa has never learned how to play the piano, her playing process is completely random. More precisely, she chooses any one of the $N$ notes on the piano with equal probability, and this choice is independent of all previously chosen notes.

Alisa's good friend Mirta wants to hear a piece consisting of $M$ consecutive notes $A_1, A_2, \dots, A_M$. But since Alisa's playing is completely random, Mirta only wants to know, for every $1\leqslant i\leqslant M$, the expected number of choices Alisa makes until Mirta hears the consecutive notes $A_1, A_2, \dots, A_i$ for the first time. To avoid precision loss, take the answers modulo $\bf 10^9+7$.

Input Format

The first line contains an integer $N$, the number of notes.
The second line contains an integer $M$, the number of notes in the piece that Mirta wants to hear.
The third line contains $M$ integers $A_i$, where $A_i$ is the $i$-th note of the piece.

Output Format

Output $M$ lines, each containing a positive integer. The $i$-th line should be the expected number of choices Alisa makes until Mirta hears the consecutive notes $A_1, A_2, \dots, A_i$ for the first time, taken modulo $\bf 10^9+7$.

2
2
1 2

2
4

2
2
1 1

2
6

3
3
1 2 3

3
9
27

Hint

Constraints

For $40\%$ of the testdata, $1\leqslant M\leqslant 200$.
For all testdata, $1\leqslant N\leqslant 100$, $1\leqslant M\leqslant 10^6$, $1\leqslant A_i\leqslant N$.

Source

This problem is from COCI 2016-2017 CONTEST 7 T6 KLAVIR, with the original testdata settings and a full score of $160$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5