시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 27 8 7 31.818%

문제

이 대회가 열리는 9 월 21 일은 출제진인 다현이의 생일이다. 그래서 출제진들은 다현이를 위해 데브베이커리에서 주문한 특제 쿠키 케이크를 준비했다!

케이크는 정확히 원통형 모양이며, 원의 중심 한 곳과, 원주 위의 점 N 곳에 S 등급 이상의 쿠키 장식이 존재한다. 각 장식들을 시계방향으로 장식 1, 장식 2, ... , 장식 N 라고 부르자. 쿠키 장식은 여러 가지 종류이므로, 원주에서 인접한 두 장식은 서로 다른 종류가 되도록 하고 싶다.

케이크를 본 근우는 장난 삼아 이 케이크를 조각 내고 싶어졌다. 장식이 N 개이므로 총 N 번의 칼질을 하는데, 케이크의 중심에 있는 장식에서 둘레의 한 장식이 있는 곳으로 자른다. 첫번째로는 장식 A_1 을 자르고, 두번째로 장식 A_2 를 자르고, ... , 마지막으로 장식 A_N 을 자른다. 단, 이미 자른 장식은 케이크의 중심에 있는 장식과 종류가 달라야 한다.

근우는 여기서 의문점이 생겼다. 시간 i 까지 자른 상태에서 K 가지 장식을 이용해 케이크를 장식할 수 있는 방법의 수가 궁금해진 것이다.

옆에서 본 지훈이는 풀 수 있을 것이라고 생각했지만, 슬프게도 그는 이러한 가짓수를 구하는 방법을 알지 못하였다. 근우와 지훈이는 고민하다가 이 대회에 출전하는 참가자들 중 적어도 한 명은 이 문제를 풀 수 있을 것이라 생각하고, 이번 대회에 출제하게 되었다. 근우와 지훈이를 도와 이 문제를 풀어보자.

입력

첫째 줄에 케이크 중심을 제외한 둘레의 장식의 개수 N(N<=10^5)과, 서로 다른 쿠키 종류의 개수 K(K<=10)가 주어진다.

둘째 줄에 A_1, A_2, … , A_N 이 순서대로 주어진다.

출력

각 시간마다 조건에 맞는, 케이크를 장식할 수 있는 가짓수를 10 억 7 로 나눈 나머지를 출력한다. i 번째 줄에 시간 i-1 에서의 가짓수를 출력하라

예제 입력

3 4
1 2 3

예제 출력

96
72
48
24

힌트