题目描述
给定一个大小为 $n$ 的可重集 $S = \{a_1,a_2, \dots, a_n \}$,满足 $a_i \geq 2$。对其进行若干次如下操作:
- 设 $p_i$ 为 $a_i$ 的最小素因子
- 令 $a_i \gets \frac{a_i}{p_i}$
- 将 $\prod_{i = 1}^{|S|}p_i$ 加入集合 $S$
- 将集合 $S$ 中的 1 删去
给定 $m$,求出进行了 $m$ 次操作后的集合 $S$,每个元素对 $10^9 + 7$ 取模后输出。
输入格式
第一行:两个整数 $n, m$。 第二行:$n$ 个整数 $a_1, a_2, \dots, a_n$。
输出格式
第一行:一个整数 $k$,表示 $m$ 次操作后可重集的大小。 第二行:$k$ 个整数,表示可重集的元素对 $10^9 + 7$ 取模后的值。元素可按任意顺序输出。
样例输入 1
4 3
2 3 4 5
样例输出 1
3
2 4 15
样例输入 2
10 100
3 5 6 7 10 12 19 23 27 36
样例输出 2
6
3 23 45 120 126 684
数据范围
对于所有数据,满足 $1 \leq n \leq 10^4, 2 \leq a_i \leq 10^9, 1 \leq m \leq 10^{18}$。
对于子任务 1,满足 $n \times m < 10^5$。
对于子任务 2,满足 $n = 1$。
对于子任务 3,满足 $n \leq 100$。
对于子任务 4,满足 $n \leq 2000$。
对于子任务 5,无特殊限制。