f와 g

시간 제한3초메모리 제한512 MB

요약

N개의 정수와 T, K가 주어질 때 g(T,k)=합_{x=0}^{T} 합_i (x+a_i)^k 를 0부터 K까지 모든 k에 대해 10^9+7로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 10점
유형: 수학, 조합론, 분할 정복, 정수론
정답자: 아직 제출이 없습니다

문제

\uC815\uC218 $N$ \uAC1C $a_1, a_2, \dots, a_N$ \uC774 \uC8FC\uC5B4\uC9C4\uB2E4. \uD568\uC218 $f$ \uC640 $g$ \uB97C \uB2E4\uC74C\uACFC \uAC19\uC774 \uC815\uC758\uD55C\uB2E4.

[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)]

\uC815\uC218 $T$ , $K$ \uC640 \uC218\uC5F4 $a_1, a_2, \dots, a_N$ \uC774 \uC8FC\uC5B4\uC9C8 \uB54C, \uBAA8\uB4E0 \uC815\uC218 $i$ \uC5D0 \uB300\uD574 $g(T,i)$ \uB97C $10^9+7$ \uB85C \uB098\uB208 \uB098\uBA38\uC9C0\uB97C \uAD6C\uD558\uB77C. \uC5EC\uAE30\uC11C $0 \le i \le K$ \uC774\uB2E4.

입력

\uCCAB\uC9F8 \uC904\uC5D0 \uC815\uC218 $N$ , $K$ , $T$ \uAC00 \uC8FC\uC5B4\uC9C4\uB2E4.

\uB458\uC9F8 \uC904\uC5D0 \uC815\uC218 $a_1, a_2, \dots, a_N$ \uC774 \uC8FC\uC5B4\uC9C4\uB2E4.

출력

$g(T,0), g(T,1), \dots, g(T,K)$ \uB97C $10^9+7$ \uB85C \uB098\uB208 \uB098\uBA38\uC9C0\uB97C \uACF5\uBC31 \uD55C \uCE78\uC73C\uB85C \uAD6C\uBD84\uD574 \uCD9C\uB825\uD55C\uB2E4.

제한

$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

예제 1
입력
```
2 3 4
0 1
```
예상 출력
```
10 25 85 325
```