피아노

시간 제한1초메모리 제한64 MB

요약

확률이 같은 N개의 건반 음이 있을 때, 고정된 M개 음렬이 처음 나타날 때까지의 기대 타건 수를 모든 접두사에 대해 구한다.

난이도: 어려움10점 중 8점
유형: 문자열 매칭, 동적 계획법, 확률, 누적 합
정답자: 아직 제출이 없습니다

문제

어린 알리사는 손가락 하나로만 피아노를 치는 것을 좋아한다. 안타깝게도 알리사는 피아노를 배운 적이 없어서 연주가 완전히 무작위이다. 정확히 말하면, 알리사는 음을 하나 고를 때마다 이전에 친 음과 상관없이 $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$ 로 나눈 나머지를 출력한다.

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

예제3

예제 1
입력
```
2
2
1 2
```
예상 출력
```
2
4
```
예제 2
입력
```
2
2
1 1
```
예상 출력
```
2
6
```
예제 3
입력
```
3
3
1 2 3
```
예상 출력
```
3
9
27
```