#P17945. Senren Banka

Senren Banka

Senren Banka

一个游戏有 nn 道选择关卡。每一轮从第 11 关开始,答对第 ii 关后才能继续第 i+1i+1 关。任意一关答错,该轮立即结束,下一轮重新从第 11 关开始。某一轮连续答对全部 nn 关后,游戏首次通关。

AI 会根据过去的尝试学习:第 jj 次尝试第 ii 关时,答对的概率为 pi,min⁡(m,j)p_{i,\min(m,j)}。各关的尝试次数独立累计,失败重开一轮不会清空计数。

求首次通关所需轮数的期望,对 998244353998244353 取模。

输入格式

本题只有一组数据。

第一行包含两个整数 n,mn,m,1≤n≤201\le n\le20,1≤m≤5×1041\le m\le5\times10^4。

接下来 nn 行,每行 mm 个整数 pi,1′,…,pi,m′p'_{i,1},\ldots,p'_{i,m},满足 1≤pi,j′≤1001\le p'_{i,j}\le100,实际概率为

pi,j=pi,j′100.p_{i,j}=\frac{p'_{i,j}}{100}.

不保证这些概率随尝试次数单调。

输出格式

输出一个整数,表示所求期望对 998244353998244353 取模的结果。分数按分母的模逆元解释。

样例 1

1 1
50
2

样例 2

2 2
25 50
50 25
499122183

样例 3

10 10
1 2 3 4 5 6 8 7 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
473598335