该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

愿此行终抵群星（star）

时间限制：$2s$，空间限制：$512MB$

题目描述

​ 你正乘坐着星穷列车造访寓居宇宙的万象世界，列车进入了一个 $k$ 维空间。

​ 在这片空间下，每一个点可以看作是一个 $k$ 维坐标。列车处在 $(0,0,...,0)$ 点，位于 $(s_1,s_2,...,s_k)$ 有一颗星球正处于“星核”引发的危机之中，列车需要前往这颗星球解救上面的文明。假如列车现在的坐标是 $(x_1, x_2,...,x_k)$，它可以到达 $(x_1+1,x_2,...,x_k),(x_1,x_2+1,...,x_k),...,(x_1,x_2,...,x_k+1)$ 这 $k$ 个点中的一个，终点是 $(s_1,s_2,...,s_k)$。

​ 然而，这片空间也遭到了反物质军团的入侵，空间中的 $n$ 个点 $(a_{11}, a_{12},...a_{1k}),(a_{21}, a_{22},...a_{2k}),...,(a_{n1}, a_{n2},...a_{nk})$ 被反物质军团占领，为了尽快地到达目的星球，需要绕过这些点。

​ 现在请你计算出有多少种不同的方案可以在不经过这 $n$ 个点的情况下到达目的星球，答案可能很大，请对 $998244353$ 取模。

输入格式

​ 输入文件名为 $star.in$ 。

​ 第一行包含两个正整数 $k,\ n$，空间维度和被占领的点数。

​ 第二行包含 $k$ 个整数，$s_1,s_2,...,s_k$ ，表示目标星球的坐标。

​ 接下来 $n$ 行，每行包含 $k$ 个整数，$a_{i1}, a_{i2},...,a_{ik}$ ，表示被占领点的坐标。

输出格式

​ 输出文件名为 $star.out$。

​ 输出一行正整数表示方案数，对 $998244353$ 取模。

样例

样例1

输入数据

2 0
2 1

输出数据

3

样例解释

​ 三条路径分别为 $(0,0)\rightarrow(0,1)\rightarrow(1,1)\rightarrow(2,1)$ ，$(0,0)\rightarrow(1,0)\rightarrow(1,1)\rightarrow(2,1)$ ， $(0,0)\rightarrow(1,0)\rightarrow(2,0)\rightarrow(2,1)$ 。

样例2

输入数据

2 1
2 2
1 1

输出数据

2

样例解释

​ 两条路径分别为 $(0,0)\rightarrow(0,1)\rightarrow(0,2)\rightarrow(1,2)\rightarrow(2,2)$ ， $(0,0)\rightarrow(1,0)\rightarrow(2,0)\rightarrow(2,1)\rightarrow(2,2)$ 。

样例3

输入数据

3 2
2 2 1
0 0 1
1 2 1

输出数据

15

数据范围

​ 设 $m = max(s_1, s_2,...,s_k)$ 。

​ 对于前 $10\%$ 的数据，满足 $k = 2,\ n = 0,\ m\le5000$ 。

​ 对于前 $30\%$ 的数据，满足 $k = 2,\ m\le5000$ 。

​ 对于另 $20\%$ 的数据，满足 $k = 2,\ n = 0$ 。

​ 对于另 $20\%$ 的数据，满足 $k = 2$ 。

​ 对于另 $10\%$ 的数据，满足 $k = 3,\ n = 0$。

​ 对于 $100\%$ 的数据，满足 $2\le k\le10,\ 0\le n\le5000,\ 1\le m\le10^5,\ 0\le a_{ik}\le s_{ik}$ ，保证 $n$ 个点以及目标点都互不相同 。