← 返回题目列表

Codeforces · 2200/G

G. 运算排列

中文机器翻译题面 查看原题

AksLolCoding 有一个整数 $$$x$$$ 和一个 $$$n$$$ 操作列表。每个操作都是一个以其中一个符号开头的字符串 +、-、x、 or / (分别代表加法、减法、乘法和实数除法),后面紧跟一个正整数 $$$y$$$ ($$$1 \leq y \leq 10^9$$$)。例如,操作 x3 表示 $$$x$$$ 乘以 $$$3$$$。

AksLolCoding 将随机排列操作,然后按排列顺序将所有操作按顺序应用于 $$$x$$$。帮助 AksLolCoding 计算 $$$x$$$ 模 $$$10^9+7$$$ 的预期$$$^{\text{*}}$$$ 最终值。

正式地,令 $$$M = 10^9 + 7$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not\equiv 0 \pmod M$$$。输出等于 $$$p \cdot q^{-1} \pmod M$$$ 的整数。换句话说,输出这样一个整数 $$$a$$$ 使得 $$$0 \le a \lt M$$$ 和 $$$a \cdot q \equiv p \pmod M$$$ 。

$$$^{\text{*}}$$$$$$x$$$ 的预期最终值是 $$$x$$$ 在所有 $$$n!$$$ 排列中的最终值的平均值。

输入

第一行包含一个整数 $$$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 用于表示乘法,而不是 *

输出

对于每个测试用例,输出一个整数:$$$x$$$ 模 $$$10^9+7$$$ 的预期最终值。

示例

输入
复制

4
2 10
x2 -10
4 2
+6 +7 /1 -13
8 1
+1 x2 x3 +4 +5 +6 -7 -8
9 864209753
-918273645 x564738291 /365107362 x734582911 -654321789 x998244353 +172519103 /482193765 /482091376

输出
复制

5
2
166666677
601980218

注意

在第一个测试用例中,$$$x$$$ 可以是 $$$(10\cdot 2)-10=10$$$ 或 $$$(10-10)\cdot 2=0$$$,导致预期值为 $$$5$$$。

在第二个测试用例中,所有可能的排列都会导致 $$$x=2$$$。

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