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.

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

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