f and g

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

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

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

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

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