# String Power STRPOW Solution

Page Contents

## String Power STRPOW April Long Challenge 2021

Chef has been recently studying strings and probabilities and he came up with a problem for you.

Consider an alphabet with N characters (denoted by c1,c2,…,cN). For each valid i, the character ci has a power ai; the power of a string that contains only characters from this alphabet is the sum of their powers (if a character occurs multiple times, its power also occurs in the sum multiple times). For example, the power of a string c1c2c3 is a1+a2+a3 and the power of a string c1c2c1 is 2⋅a1+a2.

Also, for each valid i, you are given two parameters pi and Bi, where pi is a non-negative integer and Bi∈{0,1}. For an integer K, we can construct a random string S with length K in the following way:

Define R=∑i=1Npi.
First, each of the K characters of S is chosen independently. For each valid i and j, the i-th character of S is cj with probability pj/R.
Then, for each valid i, we compute the number of occurrences of ci in S and if the parity of this number of occurrences (i.e. its remainder modulo 2) is different from Bi, we discard the string S and try to construct a new random string S from the beginning.
Otherwise (if the parities of occurrences of all characters match the sequence B), we have constructed the random string S.
All parameters are chosen in such a way that there is at least one string we can generate without discarding it. In particular, R>0.
What is the expected value of the power of the constructed string S? You need to answer Q queries. In each query, you are given a different value of K and you should find the expected power.

For each query, it can be proved that the expected power can be represented as a fraction PQ, where P and Q are non-negative integers and Q is coprime with 998,244,353. You need to compute P⋅Q−1 modulo 998,244,353, where Q−1 denotes the multiplicative inverse of Q modulo 998,244,353.

Input
The first line of the input contains a single integer N.
N lines follow. For each valid i, the i-th of these lines contains three space-separated integers ai, pi and Bi.
The next line contains a single integer Q.
Q lines follow. Each of these lines contains a single integer K describing a query.
Output
For each query, print a single line containing one integer P⋅Q−1 modulo 998,244,353.

Constraints
1≤N≤2,000
1≤ai≤4⋅108 for each valid i
0≤pi≤2,000 for each valid i
1≤R≤2,000
Bi∈{0,1} for each valid i
1≤Q≤2⋅104
1≤K≤4⋅108
Subtask #1 (2 points, time limit 1 second): N,K≤15
Subtask #2 (8 points, time limit 1.5 seconds):

K≤2,000
Q≤104
Subtask #3 (10 points, time limit 1.5 seconds): N,R≤400
Subtask #4 (80 points, time limit 2.5 seconds): original constraints

Example Input
2
1 1 0
2 2 1
2
1
3
Example Output
2
855638022
Explanation
In the first query, we can only generate the one-character string c2. Therefore, the expected power is 2.

In the second query, we can generate the following strings:

c1c1c2 with power 4 and probability 2/14
c1c2c1 with power 4 and probability 2/14
c2c1c1 with power 4 and probability 2/14
c2c2c2 with power 6 and probability 8/14
The expected power is therefore 2⋅4+2⋅4+2⋅4+8⋅62+2+2+8=367=855,638,022.