配点 : 100 点
問題文
0 以上 M 随机选择小于的整数的操作 执行 N 次。i 所选号码 A_i 什么时候 \mathrm{mex}\big(A_1,A_2,\dots,A_N\big) 的预期值为 使用 \text{mod}\,998244353 找到它。
但是, 表示\mathrm{mex}\big(A_1,A_2,\dots,A_N\big) 考虑一块分为 A_1,A_2,\dots,A_N 中不包含的最小非负整数。 您将获得
T 测试用例,因此请找到每个测试用例的答案。
期待値 \text{mod}\,998244353 的定义
可以证明,在这个问题中找到的期望值始终是一个有理数。此外,在该问题的约束下,要寻求的期望值可以表示为不可约分数。
当表示为 \frac{y}{x} 时
保证不能被 {x} 是 998244353 整除。
此时
使其满足 xz≡y\;(\text{mod}\,998244353) 喜欢满足 0 以上 998244352 的整数 z 是唯一确定的。这个
请回答 z 。
制約
- 1 \leq T \leq 3 \times 10^5
- 1 \leq N,M \leq 8000
- 输入都是整数
部分点
- 附加限制 如果正确答案是满足 T \leq 5,N \leq 100, M \leq 100 的数据集 10 点。
入力
输入是按以下格式从标准输入给出的。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出。 输出
N M
出力
T 行。 打印第i 在线 i 个测试用例的答案。
入力例 1
4 3 2 1 1 20 23 8000 8000
出力例 1
374341634 1 111675632 994279778
- 1 关于第二个测试用例, 可以被视为 A 的是 (0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) 的 8 一。每个 \mathrm{mex} 的值为 1,2,2,2,2,2,2,0 因此,要找到的期望值是 仅 \dfrac{13}{8} 。
- 2 关于第二个测试用例, 可以被视为A 的是 (0) 。因此,要找到的期望值是 1 。