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$$$ 的预期最终值。
示例
输入复制
42 10x2 -104 2+6 +7 /1 -138 1+1 x2 x3 +4 +5 +6 -7 -89 864209753-918273645 x564738291 /365107362 x734582911 -654321789 x998244353 +172519103 /482193765 /482091376
输出复制
52166666677601980218
注意
在第一个测试用例中,$$$x$$$ 可以是 $$$(10\cdot 2)-10=10$$$ 或 $$$(10-10)\cdot 2=0$$$,导致预期值为 $$$5$$$。
在第二个测试用例中,所有可能的排列都会导致 $$$x=2$$$。
在第三个测试用例中,$$$x$$$ 的期望值为$$$\frac{55}{6}$$$。