피아노

어린 알리사는 손가락 하나로만 피아노를 치는 것을 좋아한다. 안타깝게도 알리사는 피아노를 배운 적이 없어서 연주가 완전히 무작위이다. 정확히 말하면, 알리사는 음을 하나 고를 때마다 이전에 친 음과 상관없이 $N$개의 음 중 하나를 같은 확률로 고른다.

알리사의 친한 친구 미르타는 연속한 $M$개의 음으로 이루어진 곡을 듣고 싶다. 하지만 알리사가 무작위로 연주하기 때문에 미르타는 정확히 이 $M$개의 음이 연속으로 나오기까지 얼마나 기다려야 할지 모른다. 원하는 연속한 음의 배열을 처음으로 듣기까지 건반을 누르는 횟수의 기댓값을 구해 미르타를 도와주자. 호기심이 많은 미르타는 원하는 배열의 각 접두사에 대해서도 건반을 누르는 횟수의 기댓값을 알고 싶어 한다.

첫째 줄에 서로 다른 피아노 음의 개수를 나타내는 양의 정수 $N$이 주어진다. ($1 \le N \le 100$)

둘째 줄에 원하는 배열의 길이를 나타내는 양의 정수 $M$이 주어진다. ($1 \le M \le 10^6$)

셋째 줄에 $1$ 이상 $N$ 이하인 양의 정수 $M$개로 이루어진 배열이 주어진다.

$M$개의 줄을 출력한다. $i$번째 줄에는 미르타가 원하는 배열의 길이 $i$인 접두사를 처음으로 듣기까지 건반을 누르는 횟수의 기댓값을 $10^9 + 7$로 나눈 나머지를 출력한다.

건반을 누르는 횟수의 기댓값은 항상 정수이다.