题目描述

给定一个长度为 $n$，值域为 $[1,m]$ 的序列 $a$，求对于 $d\in[1,m]$ 的每一个 $d$，有多少个不同的序列 $b_{1\cdots n}$ 满足：

• $\forall i\in[1,n],b_i\in[1,m]$；
• $\gcd_{i=1}^n\{b_i\}=d$；
• 恰好 有 $k$ 个位置满足 $a_i\not =b_i$。

答案对 $10^9+7$ 取模。

输入格式

第一行三个整数 $n,m,k$。

第二行 $n$ 个整数 $a_{1\cdots n}$。

输出格式

一行共 $m$ 个整数，第 $i$ 个整数表示 $d=i$ 时的答案对 $10^9+7$ 取模后的值。

3 3 3
3 3 3

7 1 0

样例解释

当 $d=1$，$b=\{1,1,1\},\{1,1,2\},\{1,2,1\},\{1,2,2\},\{2,1,1\},\{2,1,2\},\{2,2,1\}$，共 $7$ 个。

当 $d=2$，$b=\{2,2,2\}$，共 $1$ 个。

当 $d=3$，没有满足条件的序列 $b$，共 $0$ 个。

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,m\leq 3\times 10^5$，$1\leq k\leq n$，$1\leq a_i\leq m$。