Lucky Draw and the Hidden Prize

Little Liu is a boy who loves to spend money on mobile games. Recently he became addicted to a new game where the core mechanic is continuously drawing cards. In the game, there are a total of \(N\) different cards. For the \(i\)th card, its weight \(W_i\) is not known exactly; however, through some online discussions, Little Liu learned that \(W_i\) follows a probability distribution. Specifically, for each \(i\), he knows three parameters \(p_{i,1}\), \(p_{i,2}\), \(p_{i,3}\) such that the weight \(W_i\) takes the value \(j\) with probability \(p_{i,j}\) (\(j=1,2,3\)), and obviously \(p_{i,1}+p_{i,2}+p_{i,3}=1\).

When playing, Little Liu spends 1 unit of money to draw one card. The probability to draw card \(i\) in any draw is \[ \frac{W_i}{\sum_{j=1}^{N}W_j}, \] and he continues drawing until he has obtained all \(N\) types of cards at least once. Let \(T_i\) be the time (i.e. the draw number) when he obtains card \(i\) for the first time.

The game company has set up an easter egg. They prepare \(N-1\) ordered pairs \((u_i,v_i)\). If for every such pair it holds that \(T_{u_i} < T_{v_i}\), then the company considers Little Liu extremely lucky and awards him a special prize.

The company deliberately chooses these \(N-1\) pairs such that for every nonempty proper subset \(S\) of \(\{1,2,\ldots,N\}\) there exists at least one pair \((u,v)\) satisfying either \(u\in S,\, v\notin S\) or \(u\notin S,\, v\in S\). In other words, the set of pairs forms a spanning tree when viewed as an undirected graph.

Your task is to compute the probability that Little Liu wins the lucky prize. It can be shown that the answer is a rational number; output it modulo 998244353.

Important: For each card \(i\), its weight \(W_i\) takes value \(j\) with probability \(p_{i,j}\). In this problem the probabilities are given in percentages. That is, for each \(i\) you are given three integers \(p_{i,1}\), \(p_{i,2}\), \(p_{i,3}\) (with \(p_{i,1}+p_{i,2}+p_{i,3}=100\)) representing the percentages.

Solution Idea

For a fixed assignment of weights to the \(N\) cards, the probability that card \(u\) appears before card \(v\) is \(\frac{W_u}{W_u+W_v}\). Since the events (over the \(N-1\) given pairs) occur simultaneously, the probability (conditioned on the weights) is the product \[ \prod_{(u,v)} \frac{W_u}{W_u+W_v}. \] We then take the expectation over all assignments of the weights. Since each card \(i\) takes value \(j\) with probability \(p_{i,j}/100\), the overall probability is \[ \frac{1}{100^N}\sum_{(w_1,\dots,w_N)\in\{1,2,3\}^N} \Biggl(\prod_{i=1}^{N}p_{i,w_i}\Biggr) \Biggl(\prod_{(u,v)}\frac{w_u}{w_u+w_v}\Biggr). \] Output the result modulo 998244353 (using modular inverses to handle the division).

inputFormat

The input consists of:

• The first line contains a single integer \(N\) (\(2 \le N \le 10\)). (Note: The constraints are chosen so that a brute-force solution over \(3^N\) possibilities is feasible.)
• The next \(N\) lines: the \(i\)th line contains three integers \(p_{i,1}\), \(p_{i,2}\), \(p_{i,3}\) (\(0 \le p_{i,j} \le 100\) and \(p_{i,1}+p_{i,2}+p_{i,3}=100\)).
• The following \(N-1\) lines: each contains two integers \(u\) and \(v\) (\(1 \le u,v \le N\)) representing an ordered pair. The \(N-1\) pairs satisfy the property that for every nonempty proper subset \(S\) of \(\{1,\dots,N\}\) there is an edge with one endpoint in \(S\) and the other in \(\{1,\dots,N\}\setminus S\).

outputFormat

Output a single integer — the probability that Little Liu wins the prize, modulo 998244353.

sample

2
100 0 0
100 0 0
1 2

499122177