#P18444. Rolling For Days

Rolling For Days

Rolling For Days

在游戏 TFT 中,玩家需要从商店购买单位,组成强大的阵容来对抗其他玩家。商店只会刷新一星单位;三个相同的一星单位可以合成为对应的二星单位,三个相同的二星单位又可以合成为对应的三星单位。星级更高的单位显然更强。商店刷出的单位是随机的,而刷新需要花费金币,因此即使有很多金币,也可能始终刷不到想要的单位。

原题中的游戏示例

游戏中一个令人烦恼的例子(原题配图)。

作为一位有规划的玩家,你想知道,为了完成某个特定阵容,究竟需要刷新多少次。为此,先考虑下面的简化问题。

卡池中一共有 nn 张牌,分为 mm 种,其中第 ii 种有 aia_i 张。目标阵容需要第 ii 种牌 bib_i 张。

每次刷新,从卡池中当前剩余的所有牌中等概率随机抽出一张。

  • 如果这种牌已经买够了(即已购买数量等于目标需要的数量),就立刻将这张牌放回卡池。
  • 否则,买下这张牌,并将它从卡池中移除。

求买齐全部目标牌所需的刷新次数的期望,答案对 998244353998244353 取模。尚未购买的牌仍在池中;不需要的牌被放回,不能将所有抽出的牌都视作永久移除。

形式化地,记 M=998244353M=998244353。可以证明,该期望能表示为不可约分数 p/qp/q,其中 p,qp,q 为整数且 q≢0(modM)q\not\equiv0\pmod M。输出 p⋅q−1 mod Mp\cdot q^{-1}\bmod M,即满足 0≤x<M0\le x<M 且 xq≡p(modM)xq\equiv p\pmod M 的整数 xx。

输入格式

第一行两个整数 n,mn,m,满足 1≤n≤10001\le n\le1000,1≤m≤121\le m\le12,分别表示牌的总数和种类数。

第二行 mm 个整数 a1,a2,…,ama_1,a_2,\ldots,a_m,满足 1≤ai≤n1\le a_i\le n 且 ∑i=1mai=n\sum_{i=1}^{m}a_i=n,表示每种牌的数量。

第三行 mm 个整数 b1,b2,…,bmb_1,b_2,\ldots,b_m,满足 0≤bi≤ai0\le b_i\le a_i,表示目标需要的数量。

输入只有一个测试实例。

输出格式

输出一个整数,表示所需刷新次数的期望对 998244353998244353 取模的结果。

样例 1

2 2
1 1
1 1
2

样例 2

4 2
2 2
2 1
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
265294941