有一天，魔法师小 L 看到了一个有向完全图。
图中所有边的长度都是 1，且所有边都是白色的。
现在小 L 要对这个图施展魔法，图中每条有向边分别都有一定概率变成黑色。
小 L 认为一个图是“密集的”，当且仅当只经过黑色边时，点 1 到其余所有点的最短路径长度都不超过 k（特别地，若两个点不连通则它们之间最短路径的长度视为 +\infty）。
小 L 想要知道，此时这个有向完全图有多大的概率是“密集的”呢？请你输出此概率对 998,244,353 取模的结果。
输入
第一行两个正整数 n(2\leq n\leq 12),k(1\leq k\leq n-1)。
接下来 n\times(n-1) 行，每行 4 个正整数 x,y,p,q，表示点 x 到点 y 的有向边变成黑色的概率为 \frac{p}{q}。保证 1\leq x\leq n, 1\leq y\leq n, x\neq y, 0\leq p\leq q<998,244,353,q>0，每组合法的 (x,y) 恰好出现一次。
输出
一行一个整数表示答案。
样例
| 标准输入 复制文本 |
3 1 1 2 1 2 2 1 1 2 1 3 1 3 3 1 2 3 2 3 3 4 3 2 2 5 |
| 标准输出 复制文本 |
166374059 |
提示
这个有向完全图是“密集的”，当且仅当点 1 到点 2 的有向边和点 1 到点 3 的有向边同时变成黑色，这种情况出现的概率 =\frac{1}{2}\times\frac{1}{3}=\frac{1}{6}，\frac{1}{6} \bmod 998,244,353 = 6^{998,244,351} \bmod 998,244,353 = 166,374,059。
来源
THUPC 2021 初赛