题目描述

Kamome 正在努力训练 AI 玩游戏。她让 AI 训练游戏“Senren Banka”。

这个游戏每轮有 $n$ 个选择分支。当且仅当你在一轮中正确地选择了所有分支时，才算通过游戏。每一轮都从分支 1 开始，对于 $i = 1, 2, \dots, n-1$，你必须在正确选择第 $i$ 个分支后才能选择第 $i+1$ 个分支。如果你做出错误的选择，你将进入“坏结局”，然后必须从头开始。这被视为新的一轮游戏。

Kamome 的 AI 可以从过去的经验中学习。更具体地说，如果这是你第 $j$ 次选择第 $i$ 个分支，那么 AI 以 $p_{i, \min(m, j)}$ 的概率选择正确选项。

Kamome 想知道这个 AI 第一次通过游戏需要多少个期望轮数。输出结果模 $998244353$。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 20$, $1 < m \le 5 \times 10^4$)，分别表示选择分支的数量和 AI 的阈值。

接下来的 $n$ 行，每行包含 $m$ 个整数 $p_{i,j}$ ($1 \le p_{i,j} \le 100$)，表示 $p_{i,j}$。

输出格式

输出一行包含一个整数，表示答案模 $998244353$。

样例

样例 1

输入

1 1
50

输出

2

样例 2

输入

2 2
25 50
50 25

输出

499122183

样例 3

输入

10 10
1 2 3 4 5 6 7 8 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

数据范围

$1 \le n \le 20$ $1 < m \le 5 \times 10^4$ $1 \le p_{i,j} \le 100$ 答案模 $998244353$。