配点 : 100 点
問題文
爱丽丝是 我隐藏了 (1,2,\dots,N) 的排列 给出了 P=(P_{1},P_{2},\dots,P_{N}) 是我最喜欢的。 Bob 知道如果猜中P 就能从 Alice 那里得到可乐,他决定向 Alice 提问, 然后猜中 P 。
Bob 将以下问题 M 次。 交换
- (1,2,\dots,N) 的排列 给出了 Q=(Q_{1},Q_{2},\dots,Q_{N}) 确定一个,然后问 Alice 她最喜欢的排列是否是 Q 。
这里 M \leq N 成立。
Alice 对 Bob 的问题将执行以下操作。
- P = Q ,Alice 会给 Bob 可乐。 如果是
- P \neq Q ,Alice 会把 P_{i}\neq Q_{i} 如果 i 教给 Bob。 当是
例如,P=(4,3,2,1) 的时候 Q=(4,3,1,2) 提问时,Alice 会告诉 Bob 「P_{i}\neq Q_{i} 变为 i 存在,并且在其 i 中最小的是 3 」
M 在第几次提问之后, P 即使被确定,也请注意可乐是拿不到的。
首先,Bob 对 P 没有任何信息。当 Bob 让从 Alice 那里获得可乐的概率达到最大时,该概率为 \text{mod} \;998244353 找到它。
確率 \text{mod} \;998244353 的定义
在这个问题中,求得的概率可以证明一定是有理数。另外,在这个问题的约束条件下,求得的概率可以用最简分数表示。 \frac{y}{x} 时 保证不能被 x 是 在 998244353 整除。这时, 由于只有一个 y \equiv xz \pmod{998244353} 小于 0\leq z\lt 998244353 , z 输出。制約
- 1 \leq M \leq N \leq 10^{7}
- 所有输入均为整数
部分点
- 附加限制 如果正确答案是满足 M \leq 10^{5} 的数据集 给出 70 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N M
出力
打印答案。 来自
入力例 1
2 1
出力例 1
499122177
質問 1 次提问中 P 作为可能考虑的排列有 2 种,因此,\frac{1}{2} 的概率可以获得可乐。
1 即使在第几次提问被排除, P 也可以被确定,但是请注意可乐是拿不到的。
入力例 2
1 1
出力例 2
1
1 在第几次提问一定可以获得可乐。
入力例 3
167 91
出力例 3
469117530