CF2200G.Operation Permutation

AksLolCoding has an integer $x$ and a list of $n$ operations. Each operation is a string starting with one of the symbols +,-,x, or / (representing addition, subtraction, multiplication, and real number division respectively), followed immediately by a positive integer $y$ ($1 \leq y \leq 10^9$). For example, the operation x3 represents multiplying $x$ by $3$.

AksLolCoding will randomly permute the operations and then apply all operations sequentially to $x$ in the permuted order. Help AksLolCoding compute the expected$^{\text{∗}}$ final value of $x$ modulo $10^9+7$.

Formally, let $M = 10^9 + 7$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not\equiv 0 \pmod M$. Output the integer equal to $p \cdot q^{-1} \pmod M$. In other words, output such an integer $a$ that $0 \le a \lt M$ and $a \cdot q \equiv p \pmod M$.

$^{\text{∗}}$The expected final value of $x$ is the average of the final value of $x$ over all $n!$ permutations.

AksLolCoding 有一个整数 $x$ 和一个包含 $n$ 个操作的列表。每个操作是一个字符串，以符号 +、-、x 或 /（分别表示加法、减法、乘法和实数除法）之一开头，其后紧跟着一个正整数 $y$（$1 \leq y \leq 10^9$）。例如，操作 x3 表示将 $x$ 乘以 $3$。

AksLolCoding 将随机打乱这些操作的顺序，然后按打乱后的顺序依次对 $x$ 执行所有操作。请帮助 AksLolCoding 计算 $x$ 的最终值的期望值（对所有 $n!$ 种排列取平均）模 $10^9+7$ 的结果。

形式化地，令 $M = 10^9 + 7$。可以证明答案可表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not\equiv 0 \pmod M$。请输出满足 $p \cdot q^{-1} \pmod M$ 的整数。换言之，输出满足 $0 \le a < M$ 且 $a \cdot q \equiv p \pmod M$ 的整数 $a$。

$^{\text{∗}}$ $x$ 的最终值的期望值，即对全部 $n!$ 种排列所得最终值取算术平均。

The first line contains a single integer $t$ ($1 \leq t \leq 1000$), the number of test cases.

For each test case, the first line contains two integers $n$ and $x$ ($1 \leq n \leq 3000$, $1 \leq x \leq 10^9$).

The second line of each test case contains $n$ strings, each representing an operation in the format described above.

The sum of $n^2$ over all test cases does not exceed $3000^2$.

Note: x is used to represent multiplication, not *

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $x$（$1 \leq n \leq 3000$，$1 \leq x \leq 10^9$）。

每个测试用例的第二行包含 $n$ 个字符串，每个字符串表示一个如上所述格式的操作。

所有测试用例中 $n^2$ 的总和不超过 $3000^2$。

注意：此处的 $x$ 表示乘法运算，而非 \*。

For each test case, output a single integer: the expected final value of $x$ modulo $10^9+7$.

对于每个测试用例，输出一个整数：$x$ 的最终期望值对 $10^9+7$ 取模的结果。

In the first test case, $x$ can either be $(10\cdot 2)-10=10$ or $(10-10)\cdot 2=0$, resulting in an expected value of $5$.

In the second test case, all possible permutations result in $x=2$.

In the third test case, the expected value of $x$ is $\frac{55}{6}$.

在第一个测试用例中，$x$ 的值可以是 $(10\cdot 2)-10=10$ 或 $(10-10)\cdot 2=0$，因此期望值为 $5$。

在第二个测试用例中，所有可能的排列均得到 $x=2$。

在第三个测试用例中，$x$ 的期望值为 $\frac{55}{6}$。