Expected Information Spread over Distributors

In this problem, there are (N) distributors numbered from (1) to (N) who are connected by (M) undirected trading relationships. For the (i\text{-th}) trading relationship connecting distributors (u_i) and (v_i), if one party obtains the production information of the toy “Du Yan Xiao Bao”, then with probability (\frac{p_i}{q_i}) (in (\LaTeX) as (\frac{p_i}{q_i})) the information is passed to the other party. It is guaranteed that the resulting undirected graph is connected and has no self‐loops or multiple edges.\n\nSome set of distributors (a_1, a_2,\ldots,a_k) (with (k \ge 3)) form a commercial group if and only if there exist (k) distinct trading relationships such that for each (w=1,2,\ldots,k), the (w\text{-th}) relationship connects (a_w) and (a_{((w \bmod k)+1)}). In other words, a commercial group corresponds to a simple cycle in the graph. Moreover, each distributor belongs to at most one commercial group.\n\nNow, Datalia conducts (Q) independent tests. In the (i\text{-th}) test, he reveals the production information to distributor (S_i). The information then spreads along the trading relationships (each edge works independently according to its probability). Under expectation, determine how many distributors will eventually learn the production information. It can be proved that the answer can be written as a rational number (\frac{p}{q}). You are required to output (p \cdot q^{-1} \pmod{998,244,353}).

inputFormat

The input is given as follows:\ The first line contains two integers (N) and (M) \ ((1 \le N \le 15) and (0 \le M \le \frac{N(N-1)}{2})). \ Then (M) lines follow. The (i\text{-th}) of these lines contains four integers (u_i, v_i, p_i, q_i) indicating that there is a trading relationship between distributors (u_i) and (v_i) with probability (\frac{p_i}{q_i}) ((1 \le u_i, v_i \le N, u_i \neq v_i), and the fraction is given in terms of two integers with (1 \le p_i \le q_i)).\ The next line contains a single integer (Q) ((1 \le Q \le 10)), the number of tests.\ Each of the following (Q) lines contains a single integer (S_i) ((1 \le S_i \le N)), indicating that in the (i\text{-th}) test the information is initially revealed to distributor (S_i).

outputFormat

For each test case, output a single line containing the expected number of distributors (modulo (998,244,353)) that eventually get the information, i.e. output (p\cdot q^{-1}\pmod{998,244,353}).

sample

3 2
1 2 1 2
2 3 1 2
1
1

249561090