题目描述

有 $N$ 枚编号为 $1,2,\ldots,N$ 的硬币排成一排。开始时，所有硬币均为正面朝上。

すぬけ君等概率地选择一个 $1$ 到 $N$ 的排列 $p$，并进行 $N$ 次操作。第 $i$ 次操作如下：

• 如果第 $i$ 枚硬币为反面，则什么都不做。
• 如果第 $i$ 枚硬币为正面，则先将第 $i$ 枚硬币翻面，然后再将第 $p_i$ 枚硬币翻面。

经过 $N$ 次操作后，设正面朝上的硬币有 $k$ 枚，すぬけ君可以从妈妈那里获得 $W^k$ 日元。

请计算すぬけ君最终获得金额的期望值乘以 $N!$ 后对 $998244353$ 取模的结果（可以证明该值为整数）。

输入格式

输入为一行，包含两个整数：

$N$ $W$

输出格式

输出すぬけ君最终获得金额的期望值乘以 $N!$ 后对 $998244353$ 取模的结果。

样例 1

输入

4 2

输出

90

样例 2

输入

2 100

输出

10001

样例 3

输入

200000 12345

输出

541410753

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq W < 998244353$

样例解释 1

• 当 $p=(1,4,2,3)$ 时，操作如下：
  • 第 $1$ 次操作时，第 $1$ 枚硬币变为反面，之后第 $1$ 枚硬币又变为正面。
  • 第 $2$ 次操作时，第 $2$ 枚硬币变为反面，之后第 $4$ 枚硬币变为反面。
  • 第 $3$ 次操作时，第 $3$ 枚硬币变为反面，之后第 $2$ 枚硬币变为正面。
  • 第 $4$ 次操作时，不进行任何操作。
  • 最终有 $2$ 枚硬币为正面，因此可以获得 $4$ 日元。

样例解释 3

• 不要忘记对 $998244353$ 取模。

由 ChatGPT 4.1 翻译