P7142 [THUPC 2021 Preliminary] Dense Subgraph

One day, the wizard Xiao L saw a complete directed graph. All edges in the graph have length $1$, and all edges are white. Now Xiao L wants to cast magic on this graph. Each directed edge independently has a certain probability of turning black. Xiao L considers a graph to be "dense" if and only if, when traveling using only black edges, the shortest path length from node $1$ to every other node is at most $k$ (in particular, if two nodes are not connected, the shortest path length between them is considered $+ \infty$). Xiao L wants to know: what is the probability that this complete directed graph is "dense"? Please output this probability modulo $998,244,353$.

The first line contains two positive integers $n$ ($2 \le n \le 12)$ and $k$ ($1 \le k \le n - 1$). In the next $n \times (n - 1)$ lines, each line contains four positive integers $x, y, p, q$, meaning that the probability that the directed edge from node $x$ to node $y$ turns black is $\frac{p}{q}$. It is guaranteed that $1 \le x \le n$, $1 \le y \le n$, $x \ne y$, $0 \le p \le q < 998,244,353$, $q > 0$, and each valid $(x, y)$ appears exactly once.

Output one integer in a single line, representing the answer.

**[Sample Explanation #1]** This complete directed graph is "dense" if and only if both the directed edge from node $1$ to node $2$ and the directed edge from node $1$ to node $3$ turn black. The probability of this happening is $= \frac{1}{2} \times \frac{1}{3} = \frac{1}{6}$, and $\frac{1}{6} \bmod 998,244,353 = 6^{998,244,351} \bmod 998,244,353 = 166,374,059$. **[Source]** From the preliminary round of the 2021 Tsinghua University Student Programming Contest and Intercollegiate Invitational (THUPC2021). Solutions and other resources can be found at . Translated by ChatGPT 5