题目描述

卡池里有 $n$ 张卡，卡有 $m$ 种，第 $i$ 种卡有 $a_i$ 张，对于第 $i$ 种卡，你需要 $b_i$ 张。

现在你没有手上没有卡，你要去抽卡。你的策略是这样的：

每一轮在卡池里等概率取抽一张卡（不妨记抽出来的卡种类是 $c$），如果这种 $c$ 卡的数量已经够了，也就是之前已经抽出了 $b_c$ 张种类 $c$ 的卡，那就把这次抽到的卡扔回卡池中，否则保留这张卡。

问期望抽多少轮卡才能达到你的目标，答案对 $998244353$ 取模。

输入格式

第一行一个两个整数 $n,m$。

第二行 $m$ 个整数 $a_i$。

第三行 $m$ 个整数 $b_i$。

输出格式

一个整数，表示答案。

样例

样例输入1

30 2
21 9 
16 5

样例输出1

392863631

样例输入2

100 5
10 0 59 11 20 
4 0 3 0 9

样例输出2

289262577

样例输入3

1000 12
18 5 28 258 2 184 28 145 71 55 10 196 
15 1 27 154 1 104 25 113 6 24 2 80

样例输出3

135831346

数据范围

对于所有数据，有: $n\leq 1000;m\leq 12$。

保证：$\sum_{i=1}^m a_i=n; 0\leq b_i\leq a_i$。

数据关于 $m$ 有梯度。$20$ 组数据中：

$m=2,12$ 的各有 $3$ 个。

$m=3,4,10,11$ 的各有 $2$ 个。

$m=1,5,6,7,8,9$ 的各有 $1$ 个。