Description

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$.

Input Format

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 Format

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

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

Hint

[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 https://github.com/THUSAAC/THUPC2021-pre.

Translated by ChatGPT 5