f and g

Time limit3sMemory limit512 MB

Summary

Compute g(T,k)=sum_{x=0}^{T} sum_i (x+a_i)^k mod 1e9+7 for every k from 0 to K, given N up to 1e5, K up to 5e4, T up to 1e18.

Level: Hard10 of 10
Topics: Math, Combinatorics, Divide and conquer, Number theory
Solved: No attempts yet

Problem

You are given $N$ integers $a_1, a_2, \dots, a_N$ . Define functions $f$ and $g$ as follows.

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

Given integers $T$ and $K$ , and the sequence $a_1, a_2, \dots, a_N$ , compute $g(T,i)$ modulo $10^9+7$ for every integer $i$ such that $0 \le i \le K$ .

Input

The first line contains three integers $N$ , $K$ , and $T$ .

The second line contains $N$ integers $a_1, a_2, \dots, a_N$ .

Output

Print $g(T,0), g(T,1), \dots, g(T,K)$ modulo $10^9+7$ , separated by single spaces.

Constraints

$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$

Examples1

Example 1
Input
```
2 3 4
0 1
```
Expected output
```
10 25 85 325
```