可爱の#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 |
提示:大家不要太过相信自己的常数,尽量做好常数优化。