Problem #3471 - ECNU Online Judge

单点时限: 1.0 sec

内存限制: 256 MB

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.

输入格式

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

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

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

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

输出格式

The $i$ -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.

样例

Input

3
3
1 2 3

Output

3
9
27

Input

2
2
1 1

Output

2
6

Input

2
2
1 2

Output

2
4

1 人解决，2 人已尝试。

1 份提交通过，共有 4 份提交。

9.8 EMB 奖励。

创建: 7 年，3 月前.

修改: 7 年，3 月前.

最后提交: 4 年，4 月前.

来源: COCI 2017

probabilities

3471. Klavir

输入格式

输出格式

样例

服务

开源

关于我们