题目描述

小刘同学是一个喜欢氪金手游的男孩子。
他最近迷上了一个新游戏，游戏的内容就是不断地抽卡。现在已知：

• 卡池里总共有 $N$ 种卡，第 $i$ 种卡有一个权值 $W_i$，小刘同学不知道 $W_i$ 具体的值是什么。但是他通过和网友交流，他了解到 $W_i$ 服从一个分布。

• 具体地，对每个 $i$，小刘了解到三个参数 $p{i,1},p{i,2},p_{i,3}$，$Wi$ 将会以 $p{i,j}$ 的概率取值为 $j$，保证 $p{i,1}+p{i,2}+p_{i,3}=1$。

小刘开始玩游戏了，他每次会氪一元钱来抽一张卡，其中抽到卡 $i$ 的概率为： $$\frac{W_i}{\sum_j W_j}$$ 小刘会不停地抽卡，直到他手里集齐了全部 $N$ 种卡。
抽卡结束之后，服务器记录下来了小刘第一次得到每张卡的时间 $T_i$。游戏公司在这里设置了一个彩蛋：公司准备了 $N−1$ 个二元组 $(u_i,vi)$，如果对任意的 $i$，成立 $T{ui}<T{v_i}$，那么游戏公司就会认为小刘是极其幸运的，从而送给他一个橱柜的手办作为幸运大奖。
游戏公司为了降低获奖概率，它准备的这些 $(u_i,v_i)$ 满足这样一个性质：对于任意的 $\varnothing\ne S\subsetneq{1,2,\ldots,N}$，总能找到 $(u_i,v_i)$ 满足：$u_i\in S,v_i\notin S$ 或者 $u_i\notin S,v_i\in S$。
请你求出小刘同学能够得到幸运大奖的概率，可以保证结果是一个有理数，请输出它对 $998244353$ 取模的结果。

输入格式

第一行一个整数 $N$，表示卡的种类数。
接下来 $N$ 行，每行三个整数 $a{i,1},a{i,2},a{i,3}$，而题目给出的 $p{i,j}=\frac{a{i,j}}{a{i,1}+a{i,2}+a{i,3}}$。
接下来 $N−1$ 行，每行两个整数 $u_i,v_i$，描述一个二元组（意义见题目描述）。

输出格式

输出一行一个整数，表示所求概率对 $998244353$ 取模的结果。

样例

input

2
0 0 1
1 1 0
1 2

output

524078286

$W_2$ 以 $\frac 12$ 的概率取 $1$ 或者 $2$：

• 如果 $W_2=1$，那么 $T_1<T_2$ 的概率为 $\frac 34$。
• 否则 $W_2=2$，$T_1<T_2$ 的概率为 $\frac 35$。

综合所有情况答案为 $\frac 12\left(\frac 34+\frac 35\right)=\frac{27}{40}$，你可以验证它对 $998244353$ 取模的结果确实是所给答案。

见附加文件中的 fgo2.in 与 fgo2.ans。

数据范围与提示

对于全部的测试数据，保证 $N\le 1000$，$a_{i,j}\le 10^6$。

• $20$ 分的数据，$N\le 15$。
• $15$ 分的数据，$N\le 200$，且每个限制保证 $|u_i−v_i|=1$。
• $20$ 分的数据，$N\le 1000$，且每个限制保证 $|u_i−v_i|=1$。
• $15$ 分的数据，$N\le 200$。
• $30$ 分的数据，无特殊限制。