题目描述

有一天，魔法师小 L 看到了一个有向完全图。

图中所有边的长度都是 $1$，且所有边都是白色的。

现在小 L 要对这个图施展魔法，图中每条有向边分别都有一定概率变成黑色。

小 L 认为一个图是“密集的”，当且仅当只经过黑色边时，点 $1$ 到其余所有点的最短路径长度都不超过 $k$（特别地，若两个点不连通则它们之间最短路径的长度视为 $+ \infty$）。

小 L 想要知道，此时这个有向完全图有多大的概率是“密集的”呢？请你输出此概率对 $998,244,353$ 取模的结果。

输入格式

第一行两个正整数 $n$（$2 \le n \le 12)$，$k$（$1 \le k \le n - 1$）。
接下来 $n \times (n - 1)$ 行，每行 $4$ 个正整数 $x, y, p, q$，表示点 $x$ 到点 $y$ 的有向边变成黑色的概率为 $\frac{p}{q}$。保证 $1 \le x \le n$，$1 \le y \le n$，$x \ne y$，$0 \le p \le 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$。

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。