P4257 Cute #10 Number Partition

Princess Fu, who is super cute qwq, has $n$ numbers, $1 \sim n$. Each number has a value $V_i$, and you need to partition them into several sets so that each number belongs to exactly one set.

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.

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

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

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 | 1 | 1000 | 10 | 1 s | | 3 | 30 | 1 | 10000 | 10 | 1 s | | 4 | 40 | 1e9 | 1e12 | 10 | 1 s | | 5 | 50 | 1 | 1e12 | 5 | 1 s | | 6 | 50 | 1e9 | 1e12 | 5 | 1 s | | 7 | 60 | 1 | 1e12 | 5 | 2 s | | 8 | 60 | 1e9 | 1e12 | 5 | 2 s | | 9 | 70 | 1e9 | 1e12 | 20 | 10 s | | 10 | 70 | 1e9 | 1e12 | 20 | 5 s | Tip: Do not be overly optimistic about constant factors; try to optimize them. Translated by ChatGPT 5