Expected Piano Performance

Alisa, a young girl, loves to play the piano with just one finger. However, she has never learned to play the piano, so every key press is completely random. More precisely, each time she presses a key she independently and with equal probability chooses one of the $N$ tones available on the piano.

Mirta, Alisa's good friend, wishes to hear a piece consisting of a contiguous sequence of $M$ tones $A_1, A_2, \dots, A_M$. Since Alisa plays randomly, Mirta is curious about the expected number of key presses needed until she hears, for the first time, the sequence $A_1, A_2, \dots, A_i$ for each $1 \le i \le M$. To avoid issues with floating–point precision, the answer for each prefix must be given modulo $10^9+7$.

Formally, for each $i$ from 1 to $M$, let $P=A_1A_2\cdots A_i$ be the pattern. When keys are pressed one by one (each chosen uniformly at random among the $N$ tones and independently of the past), let $E(P)$ be the expected number of presses needed until the pattern $P$ appears as a contiguous subsequence for the first time. You are to compute $E(P)$ modulo $10^9+7$ for every prefix $P$ of the given sequence.

inputFormat

The input consists of two lines. The first line contains two integers $N$ and $M$: the number of piano tones and the length of Mirta’s desired sequence. The second line contains $M$ integers $A_1, A_2, \dots, A_M$, representing the sequence of tones.

outputFormat

Output $M$ lines, where the $i$-th line contains a single integer: the expected number of key presses required until the sequence $A_1, A_2, \dots, A_i$ appears for the first time, taken modulo $10^9+7$.

sample

2 2
1 2

2
4