Young Alisa likes to play the piano using only one finger. Unfortunately, Alisa never learned to play the piano, so her playing is entirely random. More precisely, any time she chooses a tone to play, she does it independently of all previous tones, and chooses each of the $N$ tones with the same probability.

Her good friend Mirta wants to listen to a composition containing $M$ consecutive tones, but since Alisa plays the piano randomly, Mirta does not know how long she will have to wait to hear an array of exactly these $M$ tones. Help Mirta determine the expected number of key presses in order to hear, for the first time, her wanted array of consecutive tones. Moreover, since Mirta is a very curious girl, she also wants to know the expected number of key presses for each prefix of her wanted array of tones.

Input Specification

The first line of input contains the positive integer $N$ $(1\le N\le 100)$, the number of different piano tones.

The second line of input contains the positive integer $M$ $(1\le M\le {10}^6)$, the length of the wanted array.

The third line of input contains the array of $M$ positive integers between $1$ and $N$.

Output Specification

The $i^{\text{th}}$ of the following $M$ lines must contain the expected number of key presses in order for Mirta to hear the prefix of length $i$ of her wanted array of tones, modulo ${10}^9+7$.

The test data will be such that the expected number of key presses will always be an integer.

Scoring

In test cases worth $64$ points in total, it will hold $1\le M\le 200$.

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