有一天，ydc 在网上乱逛的时候，发现了一场比赛。这场比赛共 $n$ 位选手参加，编号为 $1,\dots ,n$，且 ydc 的编号为 $n$。

如果你能在这场比赛中获得第 $i$ 名，那么你可以得到 $p_i$ 块软妹币作为奖金。有奖金可以拿，ydc 是自然不会放过这个便宜的，而且软妹币肯定是拿得越多越好。所以 ydc 进行了充分的研究，分别计算出了所有选手得分的概率分布（包括自己）。

这场考试的得分可以为任意 $[0,1]$ 中的实数。对于第 $i$ 个人，他得 $x$ 分的概率，与一个多项式函数 $f_i(x)$ 成正比。当然，$f_i(x)$ 的定义域为 $[0,1]$。

如果第 $i$ 个人的函数为 $f_i(x)=2$，那么他获得任意分数的概率都是相等的；如果一个人的函数为 $f_i(x)=x+1$，那么他获得 $0$ 分的概率是获得 $1$ 分的概率二分之一倍。

你需要计算的是 ydc 得到的奖金的期望。由于分数是实数所以两个人分数相等的概率为无穷小，所以无需考虑排名相等的情况。

ydc 当然早就算出来啦！但是他想考考你。

对于一个有理数一定能表示成 $\frac{a}{b}$ 的形式，其中 $a\ge 0,b>0$，且 $a,b$ 互质。对于一个质数 $p$，如果 $b$ 不是 $p$ 的倍数那么我们可以定义 $\frac{a}{b}modp$ 为使 $bx\equiv a(\mathrm{mod}p)$ 的最小非负整数 $x$。如果 $b$ 是 $p$ 的倍数那么 $\frac{a}{b}modp$ 未定义。

答案一定是个有理数，输出对 $998244353$（$7\times 17\times 2^{23}+1$，一个质数）取模后的结果（保证有定义）。

输入格式

第一行包含一个整数 $n$。

在第二行有 $n$ 个整数，第 $i$ 个数代表 $p_i$。保证 $p_1\ge p_2\ge \cdots \ge p_n$。

接下来 $n$ 行，每行第一个数为正整数 $t_i$，代表第 $i$ 个人所对应的函数是一个定义域在 $[0,1]$ 上的 $t_i-1$ 次的多项式函数，接下来 $t_i$ 个非负整数，第 $j$ 个数代表该函数中 $x^{j-1}$ 项的系数。所有系数均小于 $998244353$。

显然所有人的函数在 $[0,1]$ 的范围以内大于等于 $0$。保证所有函数在 $[0,1]$ 的范围内与 $x$ 轴所成的面积在模 $998244353$ 意义下有定义且不等于 $0$。

输出格式

输出一行，包含一个整数，表示 ydc 获得的软妹币数量的期望对 $998244353$ 取模后的结果。

样例一

input

2
2 1
1 1
2 0 1

output

665496237

限制与约定

保证数据为均匀随机生成。

对于 $1\le i\le n$ 有 $0\le p_i\le 10000$。

时间限制：$6\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

来源

中国国家集训队互测2015 - By 刘剑成

下载

样例数据下载