P7142 [THUPC 2021 初赛] 密集子图

有一天，魔法师小 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)$ 恰好出现一次。

一行一个整数表示答案。

**【样例解释 #1】** 这个有向完全图是“密集的”，当且仅当点 $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）初赛。 题解等资源可在 查看。