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

一行一个整数表示答案。

这个有向完全图是“密集的”，当且仅当点 $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$。