Description

Daniel13265 somehow found $n$ gears. The number of teeth on the $i$-th gear is a positive integer $a_i$ not exceeding $m$. He now wants to connect (assemble) $k$ of these gears together in some way.

After gears are used for a period of time, wear will occur. The wear rate of a gear set is determined by the greatest common divisor of the numbers of teeth of all gears in the set: the larger the greatest common divisor is, the more often the same teeth mesh with each other, and thus the faster the wear rate becomes. This greatest common divisor is also called the wear factor.

It is easy to compute the wear factor of a given gear set. However, Daniel13265 now wants to know the wear factors of all possible gear sets that can be assembled.

Daniel13265 knows that it is impossible to assemble a gear set with a wear factor greater than $m$. Also, since the number of possible gear sets can be very large, you only need to tell him the following instead: for every $t\in[1, m]$, output the number of gear sets that can be assembled whose wear factor is $t$, modulo $10^9+7$.

Input Format

The input has $2$ lines.

The first line contains three positive integers $n, m, k$, representing the number of gears Daniel13265 has, the maximum possible number of teeth on a gear, and the desired number of gears in the gear set.

The second line contains $n$ positive integers separated by single spaces. The $i$-th number $a_i$ denotes the number of teeth on the $i$-th gear.

Output Format

Output one line with $m$ integers. The $t$-th integer denotes the number of gear sets that can be assembled whose wear factor is $t$, modulo $10^9+7$.

5 6 2
1 2 3 4 6

6 3 1 0 0 0

Hint

Sample Explanation

There are $6$ gear sets with wear factor $1$: $(1,2),(1,3),(1,4),(1,6),(2,3),(3,4)$.

There are $3$ gear sets with wear factor $2$: $(2,4),(2,6),(4,6)$.

There is $1$ gear set with wear factor $3$: $(3,6)$.

Constraints

This problem uses bundled testdata. If you pass all test cases in a subtask, you will get the full score for that subtask.

For $100\%$ of the testdata, $1\le k\le n\le10^6$ and $1\le a_i\le m\le10^6$.

Translated by ChatGPT 5