시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 35 1 1 100.000%

문제

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

\[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$가 주어진다.

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

출력

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

제한

  • $1 \le N \le 10^5$
  • $1 \le K \le 5 \cdot 10^4$
  • $1 \le T \le 10^{18}$
  • $0 \le a_i < 10^9 + 7$

예제 입력 1

2 3 4
0 1

예제 출력 1

10 25 85 325