Description

We stipulate:

1. A prime number can only be placed in the same set with prime numbers.
2. A composite number can only be placed in the same set with composite numbers ($1$ is considered composite).
3. Let the union of all prime-number sets be $U$ (i.e., the union of all prime-number sets including $S$). For each prime-number set $S$, define its value as:

$$V_S=\frac {(\sum_{i\in S}V_i)^p} {\prod_{i\in U}V_i}.$$

4. For each composite-number set $S$, define its value as follows:

Let $k=|S|$. Use these $k$ numbers as the weights of $k$ edges to connect $k+1$ vertices, forming a tree. For a permutation $P(1 \sim k+1)$, the value is:

$$V_P=\sum_{i=1}^{k} f(P_i,P_{i+1}),$$

where $f(u,v)$ is the maximum edge weight on the path $(u,v)$.

The value of the set $S$ is:

$$V_S=E(\min\{V_P\})\times|S|,$$

where $E(X)$ denotes the mathematical expectation of $X$ over all possible labeled unrooted trees, and the $\min$ is taken over all possible $P$. Here, all elements in the set are distinct, i.e., all edges are distinct.

5. The value of a partition scheme is defined as the product of the values of all sets.
6. Two partition schemes are the same if and only if their sets correspond exactly and the relative order of the prime-number sets is the same.

Now, given $n, p$ and $V_i$, please compute the sum of values over all valid and distinct partition schemes.

Take the result modulo $10^9+7$. For division, please use multiplicative inverses.

Input Format

The first line contains two positive integers $n, p$.

The second line contains $n$ positive integers $V_i$.

Output Format

Output a single non-negative integer: the answer modulo $10^9+7$.

4 1
1 2 3 4

333333359

Hint

Sample Explanation

There are the following $6$ partition schemes:

1. $(2,3)$ and $(1,4)$. The value of $(2,3)$ is ${\dfrac 5 6}$, the value of $(1,4)$ is $10$, and the total value is ${\dfrac {25} 3}$.
2. $(2),(3)$ and $(1,4)$. The value of $(2)$ is $1$, the value of $(3)$ is ${\dfrac 1 2}$, the value of $(1,4)$ is $10$, and the total value is $5$.
3. $(3),(2)$ and $(1,4)$. The value of $(3)$ is $1$, the value of $(2)$ is ${\dfrac 1 3}$, the value of $(1,4)$ is $10$, and the total value is ${\dfrac {10} 3}$.
4. $(2,3)$ and $(1),(4)$. The value of $(2,3)$ is ${\dfrac 5 6}$, the value of $(1)$ is $1$, the value of $(4)$ is $4$, and the total value is ${\dfrac {10} 3}$.
5. $(2),(3)$ and $(1),(4)$. The value of $(2)$ is $1$, the value of $(3)$ is ${\dfrac 1 2}$, the value of $(1)$ is $1$, the value of $(4)$ is $4$, and the total value is $2$.
6. $(3),(2)$ and $(1),(4)$. The value of $(3)$ is $1$, the value of $(2)$ is ${\dfrac 1 3}$, the value of $(1)$ is $1$, the value of $(4)$ is $4$, and the total value is ${\dfrac 4 3}$.

Therefore, the sum of values over all partition schemes is ${\dfrac {70} 3}$. After taking modulo $10^9+7$, the result is $333333359$.

Constraints

For $100\%$ of the testdata, $1 \le n \le 70$, $1 \le V_i \le 10^{12}$.

The table below gives the specific constraints for each test point (all are upper bounds). To prevent stressing the OJ, the testdata is compressed and the scores are adjusted; see the table for details.

Data ID	n	p	V_i	Score per test point	Time limit
1	10	1	100	10	1 s
2	20		1000
3	30		10000
4	40	1e9	1e12
5	50	1		5
6		1e9
7	60	1			2 s
8		1e9
9	70			20	10 s
10					5 s

Tip: Do not be overly optimistic about constant factors; try to optimize them.

Translated by ChatGPT 5