题目背景

本题为 CF1210F2 的加强版。

题目描述

有一张由 $n$ 个左部点和 $m$ 个右部点构成的二分图，给定一个 $n\times m$ 的矩阵 $p$，第 $i$ 个左部点和第 $j$ 个右部点之间有 $\frac{p_{i,j}}{100}$ 的概率存在一条边。

请求出这张二分图的最大匹配的期望值。答案对 $998244353$ 取模。

输入格式

第一行输入一个正整数 $T$，表示测试数据组数。

对于每组测试数据，第一行输入两个正整数 $n,m$ 表示两部分的点数。

接下来 $n$ 行，第 $i$ 行 $m$ 个非负整数 $p_{i,1},p_{i,2},\cdots,p_{i,m}$，表示存在边的概率。

输出格式

输出 $T$ 行，每行一个非负整数，表示最大匹配的期望。

4
2 2
100 100
0 100
2 2
50 50
50 50
3 3
3 1 4
1 5 9
2 6 5
4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20

2
623902722
817979314
671293894

提示

【样例解释】

对于第二组数据，分类讨论 $16$ 种情况：

• 最大匹配为 $0$ 的有 $1$ 种；
• 最大匹配为 $1$ 的有 $8$ 种；
• 最大匹配为 $2$ 的有 $7$ 种；

每种情况的出现概率都是 $\frac{1}{16}$，故答案为 $\frac{1\times8+2\times7}{16}=\frac{11}{8}$。

【数据范围】

对于所有数据，$1\le T\le 15$，$1\le n,m\le 8$，$0\le p_{i,j}\le 100$。

本题共有 $10$ 个测试点，每个 $10$ 分，第 $i$ 个测试点满足 $n,m\le\min(i,8)$。