Counting Cases

Time limit1sMemory limit1024 MB

Summary

Given N rabbits that each pick a value from the set X, count the assignments whose product equals k for every k from 1 to K, modulo 1e9+7.

Level: Hard8 of 10
Topics: Number theory, Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

The rabbit kingdom has $N$ rabbits, numbered from $1$ to $N$ . Rabbits like integers. The integer that rabbit $i$ likes most is $r_i$ . Rabbits do not reveal their favorite integers. Two different rabbits may have the same favorite integer.

A bear that infiltrated the rabbit kingdom found out that rabbits like only the integers in the set $X=\{x_1,x_2,\cdots ,x_M\}$ . For every $i$ , the favorite integer $r_i$ of rabbit $i$ is one of the $M$ integers in $X$ .

The potential of the rabbit kingdom is $\prod_{i=1}^{N}{r_i}$ . For each integer $k$ with $1\le k\le K$ , the bear wants to count the cases in which the potential of the rabbit kingdom is $k$ . Two cases are different if the favorite integer $r_i$ of some rabbit $i$ is different.

Let $f(k)$ be the number of cases in which the potential of the rabbit kingdom is $k$ . Find $f(1), f(2), \cdots, f(K)$ .

Input

The first line contains $N$ , $M$ , and $K$ , separated by spaces. $(1\le N\le 10^9;$ $1\le M,K\le 2\times 10^5)$

The second line contains $x_1, x_2, \cdots, x_M$ , separated by spaces. $(1\le x_i\le 10^9;$ $x_i<x_{i+1})$

All numbers in the input are integers.

Output

On the first line, print $f(1), f(2), \cdots, f(K) \pmod{1\,000\,000\,007}$ , separated by spaces.

Examples3

Example 1
Input
```
2 3 5
1 2 3
```
Expected output
```
1 2 2 1 0
```
Example 2
Input
```
2 2 6
2 3
```
Expected output
```
0 0 0 1 0 2
```

Example 3

Input

100 5 6
1 2 3 5 6

Expected output

1 100 100 4950 100 10000