借书

题目

题目描述

大连市第0x18中学是一所历史悠久的学校。学校规模宏大，足足有$n$个年级($n \le 50$)，从招收第一届学生至今，$m$年时光已悄然过去($m \le 10^9$)。

在这$m$年的悠久历史中，一位物理教师始终奋战在教学第一线，他的名字叫岳云鹏。岳老师每年都会突然要求一年级新生第二天带一本还没发的物理教材来上课，这本书往往全大连都买不着，所以每年一年级新生都要向剩下的$n - 1$个年级的学长们借书。由于与学长们不熟，每届新生都会随机选择$n - 1$个年级中的一个年级的学长。约定：$m$年前的第1届新生没有借到书；每年，除了一年级新生，任意一名学生手里都有书。

学长们也有过青葱岁月，当年自己借书的经历让学长们耿耿于怀，影响着他们是否愿意将书借给新生；另外，现在他们所处的年级对他们的选择也有影响。具体来说，任意一位升到$i$年级的学长（所有学生每年升一级），如果自己一年级的时候借到了书，则这次向新生借书的概率是$a[i]$；如果当年没借到，则这次向新生借书的概率是$b[i]$。

现在，胡小兔作为学校历史上的第$m$届的一名新生，正在向学长借书。请问她成功借到书的概率？

输入

第一行：两个整数$n$, $m$，意义如上文所述
第二行至第n行：第$i$行四个整数$a1, a2, b1, b2$，则$a[i] = \frac{a1}{a2}, b[i] = \frac{b1}{b2}$。

输出

一行，一个整数$p$。若胡小兔借到书的概率是$\frac{p1}{p2}$，则输出的整数$p$应保证$p1 \% P == p2 * p \% P$，其中$P = 998244353, 0 \le p \lt P$。

提示：p就是p1 * (p2的逆元）。

样例

样例输入

3 4
1 3 1 2
2 5 3 4

样例输出

354931326

样例解释

有3个年级，共4届学生。
第一年：第1届学生入学，没有借到书。
第二年：第2届学生入学。第1届学生在2年级，由于第1届学生没借到书，他们有$\frac{1}{2}$的可能性把书借给第2届，则第2届有$\frac{1}{2}$的可能借到书。
第三年：第3届学生入学。第2届在2年级，第2届学生有$\frac{1}{2} * \frac{1}{3} + \frac{1}{2} * \frac{1}{2} = \frac{5}{12}$可能把书借给第3届；第1届学生在3年级，有$\frac{3}{4}$ 可能把书借给第3届；则第3届有$\frac{1}{2} * \frac{5}{12} + \frac{1}{2} * \frac{3}{4} = \frac{7}{12}$可能借到书。
第四年：第1届毕业，第4届入学。第3届在2年级，有$\frac{7}{12} * \frac{1}{3} + \frac{5}{12} * \frac{1}{2} = \frac{29}{72}$ 可能把书借给第4届；第2届在3年级，有$\frac{1}{2} * \frac{2}{5} + \frac{1}{2} * \frac{3}{4} = \frac{23}{40}$ 可能把书借给新生，则第4届有$\frac{1}{2} * \frac{29}{72} + \frac{1}{2} * \frac{23}{40} = \frac{22}{45}$可能借到书。
所以答案是$22 * 45^{998244353 - 2} \mod 998244353 = 354931326$。

数据范围

$2 \le n \le 50$
$1 \le m \le 10^9$
$1 \le a1 \le a2 \le 10^9, 1 \le b1 \le b2 \le 10^9$