可爱の#10数字划分

题目背景

可可可可可可爱的付公主 qwq 有 $n$ 个数,$1\sim n$,每个数都有价值 $V_i$,你要将它们划分成若干个集合,每个数属于一个集合。

题目描述

我们这里规定: 1. 质数只能和质数分在同一个集合。 2. 合数只能和合数分在同一个集合($1$ 也算在合数内)。 3. 我们假设目前所有质数集合的并集为 $U$(也就是之前所有质数集合以及 $S$ 的并集),每个质数集合 $S$ 的价值定义如下: $$V_S=\frac {(\sum_{i\in S}V_i)^p} {\prod_{i\in U}V_i}$$ 4. 我们定义每个合数集合 $S$ 的价值如下: 令 $k=|S|$,我们用这 $k$ 个数分别作为 $k$ 条边的权值,连接 $k+1$ 个点,构成一棵树。对于一个排列 $P(1\sim k+1)$,价值为: $$V_P=\sum_{i=1}^{n-1} f(P_i,P_{i+1})$$ 其中 $f(u,v)$ 为路径 $(u,v)$ 上最大的边权。 集合 $S$ 的价值为: $$V_S=E(\min\{V_P\})\times|S|$$ 其中 $E(X)$ 代表 $X$ 的数学期望,期望是针对所有可能的有标号无根树,$\min$ 是针对所有可能的 $P$。这时集合内所有元素都不同,也就是所有边不同。 5. 一个划分方案的价值定义为所有集合的价值的乘积。 6. 两个划分方案相同当且仅当它们中所有集合对应相同,且质数集合的相对顺序相同。 现在给定 $n,p$ 和 $V_i$,请你求出所有合法的不同划分方案的价值之和。 结果对 $10^9+7$ 取模,除法请使用乘法逆元。

输入输出格式

输入格式


第一行输入两个正整数 $n,p$。 第二行输入 $n$ 个正整数 $V_i$。

输出格式


共一行一个非负整数,代表答案对 $10^9+7$ 取模的结果。

输入输出样例

输入样例 #1

4 1
1 2 3 4

输出样例 #1

333333359

说明

### 样例解释 有以下 $6$ 种划分方案: 1. $(2,3)$ 和 $(1,4)$。$(2,3)$ 的价值为 ${\dfrac 5 6}$,$(1,4)$ 的价值为 $10$,总价值为 ${\dfrac {25} 3}$。 2. $(2),(3)$ 和 $(1,4)$。$(2)$ 的价值为 $1$,$(3)$ 的价值为 ${\dfrac 1 2}$,$(1,4)$ 的价值为 $10$,总价值为 $5$。 3. $(3),(2)$ 和 $(1,4)$。$(3)$ 的价值为 $1$,$(2)$ 的价值为 ${\dfrac 1 3}$,$(1,4)$ 的价值为 $10$,总价值为 ${\dfrac {10} 3}$。 4. $(2,3)$ 和 $(1),(4)$。$(2,3)$ 的价值为 ${\dfrac 5 6}$,$(1)$ 的价值为 $1$,$(4)$ 的价值为 $4$,总价值为 ${\dfrac {10} 3}$。 5. $(2),(3)$ 和 $(1),(4)$。$(2)$ 的价值为 $1$,$(3)$ 的价值为 ${\dfrac 1 2}$,$(1)$ 的价值为 $1$,$(4)$ 的价值为 $4$,总价值为 $2$。 6. $(3),(2)$ 和 $(1),(4)$。$(3)$ 的价值为 $1$,$(2)$ 的价值为 ${\dfrac 1 3}$,$(1)$ 的价值为 $1$,$(4)$ 的价值为 $4$,总价值为 ${\dfrac 4 3}$。 因此所有划分方案的价值和为${\dfrac {70} 3}$。对 $10^9+7$ 取模后结果为 $333333359$。 ### 数据范围 对于 $100\%$ 的数据,满足 $1\le n\le 70$,$1\le V_i\le 10^{12}$。 下表中给出了每个测试点具体的数据范围,都表示小于等于。为了防止卡 OJ,所以本题数据组数进行压缩,分值改变,具体参照表格。 | 数据编号 | n | p | Vi | 测试点分值 | 时限 | | :------: | :--: | :--: | :---: | :--------: | :--: | | 1 | 10 | 1 | 100 | 10 | 1s | | 2 | 20 | 1 | 1000 | 10 | 1s | | 3 | 30 | 1 | 10000 | 10 | 1s | | 4 | 40 | 1e9 | 1e12 | 10 | 1s | | 5 | 50 | 1 | 1e12 | 5 | 1s | | 6 | 50 | 1e9 | 1e12 | 5 | 1s | | 7 | 60 | 1 | 1e12 | 5 | 2s | | 8 | 60 | 1e9 | 1e12 | 5 | 2s | | 9 | 70 | 1e9 | 1e12 | 20 | 10s | | 10 | 70 | 1e9 | 1e12 | 20 | 5s | 提示:大家不要太过相信自己的常数,尽量做好常数优化。