G. Операция Перестановка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

AksLolCoding имеет целое число $$$x$$$ и список из $$$n$$$ операций. Каждая операция — это строка, начинающаяся с одного из символов +,-,x, или / (представляющих сложение, вычитание, умножение и действительное деление чисел соответственно), за которым сразу следует положительное целое число $$$y$$$ ($$$1 \leq y \leq 10^9$$$). Например, операция x3 представляет собой умножение $$$x$$$ на $$$3$$$.

AksLolCoding случайным образом переставит операции, а затем последовательно применит все операции к $$$x$$$ в переставленном порядке. Помогите AksLolCoding вычислить ожидаемое$$$^{\text{∗}}$$$ конечное значение $$$x$$$ по модулю $$$10^9+7$$$.

Формально, пусть $$$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}$$$.