시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB258729.167%

문제

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

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

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

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

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

입력

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

둘째 줄에 A1, A2, … , AN 이 순서대로 주어진다. (1 ≤ Ai ≤ N)

출력

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

예제 입력 1

3 4
1 2 3

예제 출력 1

96
72
48
24

출처

University > KAIST > 2016 KAIST 6th ACM-ICPC Mock Competition B번

  • 문제를 만든 사람: jihoon