Piano

Time limit1sMemory limit64 MB

Summary

Given N equally likely piano tones, find the expected number of presses until a fixed M-tone sequence appears, for every prefix of it.

Level: Hard8 of 10
Topics: String matching, Dynamic programming, Probability, Prefix sum
Solved: No attempts yet

Problem

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, every time she chooses a tone to play, she chooses it independently of all previous tones, and each of the $N$ tones has the same probability.

Her good friend Mirta wants to listen to a composition made of $M$ consecutive tones. Since Alisa plays randomly, Mirta does not know how long she will have to wait to hear exactly these $M$ tones in a row. Help Mirta find the expected number of key presses until she hears her wanted array of consecutive tones for the first time. Mirta is also very curious, so she wants to know the expected number of key presses for each prefix of her wanted array of tones as well.

Input

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

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

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

Output

Print $M$ lines. The $i$ -th line must contain the expected number of key presses until Mirta hears the prefix of length $i$ of her wanted array for the first time, modulo $10^9 + 7$ .

The expected number of key presses is always an integer.

Examples3

Example 1
Input
```
2
2
1 2
```
Expected output
```
2
4
```
Example 2
Input
```
2
2
1 1
```
Expected output
```
2
6
```
Example 3
Input
```
3
3
1 2 3
```
Expected output
```
3
9
27
```