One day, the magician Little L saw a directed complete graph. The length of every edge in the graph is 1, and all edges are initially white. Now, Little L is going to cast a spell on this graph. Each directed edge in the graph has a certain probability of turning black. Little L considers a graph to be "dense" if and only if, considering only the black edges, the shortest path length from node 1 to all other nodes does not exceed $k$ (specifically, if two nodes are not connected, the shortest path length between them is considered $+\infty$). Little L wants to know the probability that this directed complete graph is "dense". Please output the result of this probability modulo $998,244,353$.

Input

Read data from standard input. The first line contains two positive integers $n (2 \le n \le 12)$ and $k (1 \le k \le n - 1)$. The next $n \times (n - 1)$ lines each contain four positive integers $x, y, p, q$, representing that the probability of the directed edge from node $x$ to node $y$ turning black is $\frac{p}{q}$. It is guaranteed that $1 \le x \le n, 1 \le y \le n, x \neq y, 0 \le p \le q < 998,244,353, q > 0$, and each valid pair $(x, y)$ appears exactly once.

Output

Output to standard output. A single integer representing the answer.

Examples

Input 1

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

Output 1

166374059

Note

The directed complete graph is "dense" if and only if the directed edge from node 1 to node 2 and the directed edge from node 1 to node 3 both turn black. The probability of this occurring is $\frac{1}{2} \times \frac{1}{3} = \frac{1}{6}$. $\frac{1}{6} \pmod{998,244,353} = 166,374,059$.