Gear Group Loss Factor

Daniel13265 found n gears, where the i-th gear has a_i teeth (a positive integer not exceeding m). He wants to select exactly k of these gears and mesh them together in some way. The wear‐rate of a group of gears is determined by the greatest common divisor (GCD) of the number of teeth on the selected gears. A larger GCD means the corresponding teeth mesh more frequently, which leads to a higher wear rate. This GCD is called the loss factor.

Your task is to compute, for every integer t in the range \( [1, m] \), the number of gear groups (of exactly k gears) that have a loss factor equal to \( t \). Since Daniel13265 knows that a loss factor greater than m is impossible (because each \(a_i \le m\)), you only need to provide the answers for \(t = 1, 2, \dots, m\). Output the answers modulo \(10^9+7\).

Hint: One way to solve this problem is to use the principle of inclusion–exclusion along with the Mobius function. For each candidate divisor \(d\), let \(F(d)\) be the number of ways to choose k gears from those whose tooth count is divisible by \(d\). Then the answer for loss factor equal to \(g\) is given by:

[ answer(g) = \sum_{j \ge 1,; j \cdot g \le m} \mu(j) \cdot F(j \cdot g) \mod (10^9+7). ]

inputFormat

The first line contains three integers n, m, and k (\(1 \le k \le n\)).

The second line contains n positive integers \(a_1, a_2, \dots, a_n\) where each \(a_i\) does not exceed m.

outputFormat

Output m space-separated integers. The \(t\)-th integer (for \(t=1,2,\dots,m\)) should be the number of gear groups whose loss factor is exactly \(t\), taken modulo \(10^9+7\).

sample

4 6 2
2 3 4 6

5 1 0 1 0 1