在游戏《云顶之弈》（TFT）中，玩家需要从商店购买单位来组建强大的阵容以对抗其他玩家。商店中只会刷新一星单位，三个相同的一星单位可以合成一个对应的二星单位，三个相同的二星单位可以合成一个对应的三星单位。显然，高星单位比低星单位强大得多。商店中刷新的单位是随机的，且刷新需要消耗金币。因此，即使拥有大量金币，也可能无法获得你想要的单位。

游戏中的一个恼人示例

作为一名严谨的玩家，你很好奇完成特定阵容到底需要多少次刷新。为此，你将从解决以下简化问题开始：

商店的卡池中共有 $n$ 张卡，分为 $m$ 种，其中第 $i$ 种卡共有 $a_i$ 张。你已经确定了你的目标阵容，该阵容需要第 $i$ 种卡 $b_i$ 张。每次刷新时，都会从卡池中剩余的卡里随机抽取一张，每张卡被抽到的概率相等。如果抽到的卡是不需要的（即该种卡已购买的数量等于目标阵容所需的数量），你会将这张卡放回卡池；否则，你会购买这张卡并将其从卡池中移除。你期望需要多少次刷新才能完成你的目标阵容？由于答案可能很大且无法忽略浮点误差，请输出答案对 $998244353$ 取模的结果。

形式化地，令 $M = 998244353$。可以证明答案可以表示为一个既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数且 $q \not\equiv 0 \pmod M$。输出等于 $p \cdot q^{-1} \pmod M$ 的整数。换句话说，输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod M$。

输入格式

第一行包含两个整数 $n, m(1 \le n \le 1000; 1 \le m \le 12)$，分别表示卡的总数和种类的数量。

第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m(1 \le a_i \le n, \sum_{i=1}^m a_i = n)$，表示每种卡的数量。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m(0 \le b_i \le a_i)$，表示目标阵容所需的卡数。

输出格式

输出一个整数，表示期望的刷新次数对 $998244353$ 取模的结果。

样例

样例输入 1

2 2
1 1
1 1

样例输出 1

2

样例输入 2

4 2
2 2
2 1

样例输出 2

582309210

样例输入 3

1000 12
101 43 34 281 23 24 12 25 66 222 145 24
37 43 27 257 5 11 12 19 62 41 87 13

样例输出 3

265294941