Magic Dense Graph

There is a directed complete graph with n vertices. Every directed edge has a length of $1$ and is initially white. The magician Little L casts a spell such that every directed edge turns black independently with a given probability. In other words, for every ordered pair of distinct vertices i and j, the edge from i to j becomes black with a probability given in the input.

The graph is defined to be dense if and only if, when considering only the black edges, the shortest path distance from vertex $1$ to every other vertex is at most $k$. (In particular, if some vertex is not reachable, then the distance is considered to be $+\infty$.)

Your task is to calculate the probability that after the spell the graph is dense. Since this probability is a rational number, output it modulo $998244353$.

inputFormat

The first line contains two integers $n$ and $k$ ($2 \le n \le 10$, $1 \le k \le n-1$), where $n$ is the number of vertices and $k$ is the threshold of the maximum allowed distance from vertex $1$ (using only black edges).

Then follow $n$ lines. The $i$-th of these lines contains $n$ integers. For any $i \neq j$, the $j$-th integer in the $i$-th line is an integer between $0$ and $100$ representing the percentage probability that the directed edge from vertex $i$ to vertex $j$ will turn black. (The $i$-th integer in the $i$-th line is ignored, since there is no self–loop.)

outputFormat

Output a single integer: the probability that the graph is dense, modulo $998244353$.

sample

2 1
-1 100
100 -1

1