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$.

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 *

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