Indeterministic Expression
题号：NC243984
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

For the scope of this problem, an indeterministic expression refers to an expression with no fixed value, but with uncertainties. Such uncertainties are caused by variables (i.e., symbols) with unknown values.

Examples of deterministic expression: 
2*3*5*(7+11)
2022+5-14
998244353
Examples of indeterministic expression:
a+b
x*233+42
(x+y)*(z-1)
q+q+q+q+q+q
Formally, the grammar describing a valid indeterministic expression is as below:
E ::= E '+' T | E '-' T | T
T ::= T '*' F | F
F ::= '(' E ')' | S | N

Here, S stands for symbol, which is a single lower-case Latin letter (a-z). N stands for numeric literal, which is one or several digits, without leading sign (+ or -) or leading zero.

Operations have standard priority. Multiply has the higher priority than plus and minus. Operations are left associative. Please also note that divide (/) is not supported for the scope of this problem.

输入描述:

The input starts with an integer T (1 \le T \le 100), the number of test cases.

For each test case, the first line contains an integer n (1 \le n \le 4), denoting the number of random variables.

In the next n lines, the i-th line starts with a single lower-case Latin letter s_i, and an integer k_i (1 \le k_i \le 10), which is the number of distinct possible values followed. s_1, s_2, \ldots, s_n are all different. Then k_i pairs of integers and real numbers v_{i,1},p_{i,1},\ldots,v_{i,k_i},p_{i,k_i} (0 \le v_{i,j} \le 10^9, 0 < p_{i,j} \le 1). Each of p_{i,j} must have 6 digits after their decimal points, and \sum_{j=1}^{k_i} p_{i,j} = 1. These pairs define a probability mass function: P_{s_i} (v_{i,j}) = p_{i,j}. In other words, the variable s_i has probability p_{i,j} to take the value v_{i,j} (1 \le j \le k_i).

The final line of each test case is a valid indeterministic expression, consisting of lower-case letters that has appeared in the previous n lines, digits, signs including +, -, *, (, ) . There is no extra space or other invisible characters. Each variable listed previously must appear in the expression at least once. The numeric literals appearing in the expression are all non-negative integers and never exceed 10^9.

We guarantee that the sum of expression lengths from all test cases does not exceed 1000.

输出描述:

For each test case, output the expected value of the expression modulo 998~244~353. It can be shown that the answer can be represented as \frac{P}{Q} such that P and Q are coprime integers and Q \not\equiv 0 \pmod {998~244~353}. Print the value of (P \cdot Q^{-1}) \bmod 998~244~353.
示例1

输入

复制 
2
2
a 2 1 0.500000 2 0.500000
b 2 1 0.300000 2 0.700000
a+b
3
x 1 42 1.000000
y 3 4 0.333333 6 0.333333 8 0.333334
z 2 233 0.570000 250 0.430000
x*1+(x+y)*(z-z)

输出

复制 
598946615
42

说明

For all the different symbols appearing at least once in the expression, we let them be random variables with known distributions. Specifically, for every variable, we have its probability mass function, which gives out the probability that the discrete random variable is exactly equal to some value. The denotion of P_X(b) is the probability that random variable X has value b.

Given the distributions of all variables, we ask: what is the expected value (i.e., expectation) of the whole expression. Recall that the expected value of an expression with a finite number of outcomes is an average of all possible outcomes, weighted by the probabilities of the outcomes.

For sample test case 1: The answer 598946615 \equiv \frac{16}{5} \pmod {998244353} because 598946615 \times 5 \bmod 998244353 = 16. We then explain why the answer is \frac{16}{5}.
  • The expression equals to 2 with probability 0.15. 0.3 \times 0.5 = 0.15.
  • The expression equals to 3 with probability 0.5. 0.5 \times 0.7 + 0.3 \times 0.5 = 0.5.
  • The expression equals to 4 with probability 0.35. 0.5 \times 0.7 = 0.35.

The answer is therefore 2 \times 0.15 + 3 \times 0.5 + 4 \times 0.35 = 3.2 = \frac{16}{5}.