← 返回题目列表

AtCoder · arc134_f

F. 翻转硬币

中文机器翻译题面 查看原题

分数: 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.