생일 케이크

다현이의 생일을 맞아 원통 모양 쿠키 케이크를 준비했다. 케이크에는 원의 중심에 장식이 하나 있고, 원주 위에 장식이 $N$개 있다. 원주의 장식에는 시계 방향으로 $1$번부터 $N$번까지 번호를 붙인다.

쿠키 장식의 종류는 $K$가지이고, 장식 하나마다 그중 한 종류를 고른다. 단, 원주에서 이웃한 두 장식은 종류가 달라야 한다. $N \ge 2$이면 $1 \le i \le N-1$인 $i$마다 $i$번 장식과 $i+1$번 장식이 이웃하고, $N \ge 3$이면 $N$번 장식과 $1$번 장식도 이웃한다. $N = 1$이면 원주에 이웃한 장식 쌍이 없다.

근우는 케이크를 $N$번 자른다. $i$번째 칼질은 중심의 장식에서 $A_i$번 장식까지 곧게 자른다. 한 번 잘린 장식은 중심의 장식과 종류가 달라야 한다. 즉 $i$번째 칼질을 끝낸 상태에서는 $A_1, A_2, \dots, A_i$번 장식이 모두 중심의 장식과 종류가 다르다.

아무것도 자르지 않은 상태를 시간 $0$, $i$번째 칼질을 끝낸 상태를 시간 $i$라고 하자. 각 시간마다 조건을 모두 만족하도록 장식 $N+1$개에 종류를 정하는 방법의 수를 1,000,000,007로 나눈 나머지를 구하라.

첫째 줄에 원주에 있는 장식의 개수 $N$과 쿠키 종류의 수 $K$가 주어진다. ($1 \le N \le 100000$, $1 \le K \le 10$)

둘째 줄에 $A_1, A_2, \dots, A_N$이 순서대로 주어진다. ($1 \le A_i \le N$) 같은 번호가 여러 번 나올 수 있고, 이미 잘린 장식을 다시 자르면 조건이 새로 늘어나지 않는다.

$N+1$개의 줄을 출력한다. $i$번째 줄에는 시간 $i-1$에서의 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.