$N$개의 정수 $a_1, a_2, \dots, a_N$이 주어진다. 함수 $f$와 $g$는 다음과 같이 정의한다.</p>

[f(x,k) = (x + a_1)^k + (x + a_2)^k + \cdots + (x + a_N)^k]

[g(t,k) = f(0,k) + f(1,k) + \cdots + f(t,k)]

두 정수 $T$와 $K$, 그리고 $N$개의 정수가 주어졌을때, $g(T,i)$를 $10^9+7$로 나눈 나머지를 구해보자. ($0 \le i \le k$)

입력 형식

첫째 줄에 $N$, $K$, $T$가 주어진다.</p>

둘째 줄에 $a_1, a_2, \dots, a_N$이 주어진다.

출력 형식

$g(T, 0), g(T, 1), \dots, g(T, K)$를 $10^9 +7$로 나눈 나머지를 공백 한 칸으로 구분해 출력한다.

예제 입력

2 3 4
0 1

예제 출력

10 25 85 325