题目背景

可可可可可可爱的付公主 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$ 取模的结果。

4 1
1 2 3 4

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		1000
3	30		10000
4	40	1e9	1e12
5	50	1		5
6		1e9
7	60	1			2s
8		1e9
9	70			20	10s
10					5s

提示：大家不要太过相信自己的常数，尽量做好常数优化。