Description

Student Xiao Liu is a boy who likes pay-to-win mobile games.

He recently got addicted to a new game whose content is to keep drawing cards. It is known that:

• There are $N$ types of cards in the pool. The $i$-th type of card has a weight $W_i$. Xiao Liu does not know the exact value of $W_i$, but by talking with other players he learned that $W_i$ follows a distribution.
• Specifically, for each $i$, Xiao Liu knows three parameters $p_{i,1}, p_{i,2}, p_{i,3}$. The value of $W_i$ is $j$ with probability $p_{i,j}$. It is guaranteed that $p_{i,1} + p_{i,2} + p_{i,3} = 1$.

Xiao Liu starts playing the game. Each time, he pays 1 yuan to draw one card. The probability of drawing card $i$ is:

Xiao Liu will keep drawing cards until he has collected all $N$ types of cards.

After the drawing ends, the server records the time $T_i$ when Xiao Liu gets each card for the first time. The game company sets up an easter egg: the company prepares $N - 1$ ordered pairs $(u_i, v_i)$. If for every $i$, the condition $T_{u_i} < T_{v_i}$ holds, then the company will consider Xiao Liu extremely lucky and will give him a cabinet of figurines as the lucky grand prize.

To reduce the chance of winning, these $(u_i, v_i)$ satisfy the following property: for any $\varnothing \ne S \subsetneq \{1,2,\ldots,N\}$, there always exists some $(u_i, v_i)$ such that $u_i \in S, v_i \notin S$ or $u_i \notin S, v_i \in S$.

Please compute the probability that Xiao Liu can get the lucky grand prize. It is guaranteed that the result is a rational number. Output the result modulo $998244353$.

Input Format

The first line contains an integer $N$, the number of card types.

The next $N$ lines each contain three integers $a_{i,1}, a_{i,2}, a_{i,3}$, and the probabilities in the statement are given by $p_{i,j} = \frac{a_{i,j}}{a_{i,1} + a_{i,2} + a_{i,3}}$.

The next $N - 1$ lines each contain two integers $u_i, v_i$, describing an ordered pair (see the statement for its meaning).

Output Format

Output one integer in one line, the required probability modulo $998244353$.

2
0 0 1
1 1 0
1 2

524078286

Hint

Explanation of Sample 1

$W_2$ is $1$ or $2$ with probability $\frac 12$:

• If $W_2 = 1$, then the probability that $T_1 < T_2$ is $\frac 34$.
• Otherwise, if $W_2 = 2$, then the probability that $T_1 < T_2$ is $\frac 35$.

Combining all cases, the answer is $\frac 12\left(\frac 34 + \frac 35\right) = \frac{27}{40}$. You can verify that its value modulo $998244353$ is indeed the given output.

Testdata Constraints

For all testdata, it is guaranteed that $N \le 1000$ and $a_{i,j} \le 10^6$.

• $20$ points: $N \le 15$.
• $15$ points: $N \le 200$, and every constraint satisfies $|u_i−v_i|=1$.
• $20$ points: $N \le 1000$, and every constraint satisfies $|u_i−v_i|=1$.
• $15$ points: $N \le 200$.
• $30$ points: no special constraints.

Translated by ChatGPT 5