Kamome s'efforce d'entraîner une IA à jouer à des jeux. Elle fait entraîner l'IA au jeu "Senren Banka".

Ce jeu consiste en $n$ branches de choix à chaque tour. Vous êtes considéré comme ayant réussi le jeu si et seulement si vous sélectionnez chaque branche correctement en un seul tour. Chaque tour commence par la branche 1, et pour chaque $i = 1, 2, \dots, n-1$, vous pouvez sélectionner la branche $i+1$ seulement après avoir sélectionné correctement la branche $i$. Si vous faites un mauvais choix, vous entrerez dans la "Mauvaise Fin" et devrez recommencer depuis le début. Ceci est considéré comme un nouveau tour de jeu.

L'IA de Kamome peut apprendre des choix passés. Plus précisément, si c'est la $j$-ième fois que l'IA choisit la $i$-ième branche, alors l'IA a une probabilité $P_{i,j}$ de choisir l'option correcte.

Kamome veut connaître le nombre de tours attendus pour que cette IA réussisse le jeu pour la première fois. Affichez le résultat modulo 998244353.

Entrée

La première ligne contient deux entiers $n, m$ ($1 \le n \le 20$, $1 < m \le 5 \times 10^4$), indiquant le nombre de branches de choix et le seuil de cette IA.

Les $n$ lignes suivantes, chaque ligne contient $m$ entiers $p_{i,j}$ ($1 \le p_{i,j} \le 100$), indiquant $P_{i,j} = \frac{p_{i,j}}{100}$.

Sortie

Affichez une ligne contenant un entier, indiquant la réponse modulo 998244353.

Exemples

Entrée 1

1 1
50

Sortie 1

2

Entrée 2

2 2
25 50
50 25

Sortie 2

499122183

Entrée 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

Sortie 3

473598335