分数: 1000 点
问题陈述
有 N 硬币编号 1, 2, \ldots, N 排列成一排。 最初,所有硬币都面朝上。
Snuke 选择排列 p of (1,\ldots,N) 以相同的概率,并且做 N 操作。 的 i-th 操作执行以下操作。
- 如果硬币编号 i 面朝下,什么也不做。
- 如果硬币编号 i 正面朝上,将硬币翻过来,然后将编号为1的硬币翻过来 p_i.
之后 N 操作,Snuke将收到 W^k 日元(日本货币)来自他的母亲,在哪里 k 是面朝上的硬币数量。
求 Snuke 将获得的金额的预期值,乘以 N! (可以证明这是一个整数),取模 998244353.
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W < 998244353
输入
输入由标准输入按以下格式给出:
N W
输出
打印 Snuke 将获得的金额的预期值,乘以 N!,模数 998244353.
示例输入 1
4 2
示例输出 1
90
- 当 p=(1,4,2,3),操作如下。
- 在 1-st操作,硬币编号 1 面朝下,然后硬币编号 1 面朝上。
- 在 2-nd操作,硬币编号 2 面朝下,然后硬币编号 4 面朝下。
- 在 3-rd操作,硬币编号 3 面朝下,然后硬币编号 2 面朝上。
- 在 4第次操作,什么也没做。
- 最后,两枚硬币面朝上,所以他收到 4 日元。
示例输入 2
2 100
示例输出 2
10001
示例输入 3
200000 12345
示例输出 3
541410753
- 一定要找到模值 998244353.