Xiao Liu is a boy who loves "pay-to-win" mobile games.

He has recently become obsessed with a new game that involves continuously drawing cards. It is known that: There are a total of $N$ types of cards in the card pool, and each card $i$ has a weight $W_i$. Xiao Liu does not know the specific values of $W_i$, but through discussions with other players, he has learned that $W_i$ follows a certain distribution. Specifically, for each $i$, Xiao Liu has learned three parameters $p_{i,1}, p_{i,2}, p_{i,3}$, where $W_i$ takes the value $j$ with probability $p_{i,j}$, and it is guaranteed that $p_{i,1} + p_{i,2} + p_{i,3} = 1$.

Xiao Liu starts playing the game. Each time he spends one unit of currency to draw a card, the probability of drawing card $i$ is: $$\frac{W_i}{\sum_j W_j}$$

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

After the drawing process ends, the server records the time $T_i$ at which Xiao Liu first obtained each card. The game company has included a "hidden surprise": the company has prepared $N-1$ pairs $(u_i, v_i)$. If for all $i$, the condition $T_{u_i} < T_{v_i}$ holds, the game company considers Xiao Liu to be extremely lucky and will award him a cabinet of figures as a grand prize.

To reduce the probability of winning, the company has ensured that these $(u_i, v_i)$ pairs satisfy the following property: for any $\emptyset \subsetneq S \subsetneq \{1, 2, \dots, N\}$, there always exists a pair $(u_i, v_i)$ such that $u_i \in S, v_i \notin S$ or $u_i \notin S, v_i \in S$.

Please calculate the probability that Xiao Liu wins the grand prize. It is guaranteed that the result is a rational number; please output the result modulo $998244353$.

Input

The first line contains an integer $N$, representing the number of card types. The next $N$ lines each contain three integers $a_{i,1}, a_{i,2}, a_{i,3}$, where the given $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 a pair (see the problem description for the meaning).

Output

Output a single integer representing the calculated probability modulo $998244353$.

Examples

Input 1

2
0 0 1
1 1 0
1 2

Output 1

524078286

Note 1

$W_2$ takes the value 1 or 2 with probability $\frac{1}{2}$ each: If $W_2 = 1$, the probability that $T_1 < T_2$ is $\frac{3}{4}$. Otherwise, if $W_2 = 2$, the probability that $T_1 < T_2$ is $\frac{3}{5}$. Combining all cases, the answer is $\frac{1}{2} \left( \frac{3}{4} + \frac{3}{5} \right) = \frac{27}{40}$. You can verify that its value modulo $998244353$ is indeed the given answer.

Examples

Input 2

See fgo/fgo2.in in the contestant directory.

Output 2

See fgo/fgo2.ans in the contestant directory.

Constraints

For all test data, 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 each constraint satisfies $|u_i - v_i| = 1$. 20 points: $N \le 1000$, and each constraint satisfies $|u_i - v_i| = 1$. 15 points: $N \le 200$. * 30 points: No special constraints.