题目描述

有 $N$ 张牌背面朝上排成一行，每张牌的正面写着整数 $1,2,\dots,N$ 中的一个。这些牌的顺序是从 $N!$ 种可能的顺序中均匀随机决定的。你知道整数 $1,2,\dots,N$ 中的每一个都恰好写在一张牌上，并且牌是均匀随机排列的，但除此之外你对牌面上写的整数没有任何信息。

你将进行以下游戏。

• 初始时，令变量 $x=1$。
• 只要 $x \le N$，就重复以下操作。一次操作由以下三个步骤组成。
• 指定一张牌，将它翻为正面朝上。
• 如果牌上写的整数是 $x$，吃掉这张牌，并将 $x$ 加 $1$。
• 否则，将这张牌翻回背面朝上。你可以永久记住这张牌上写的整数。

你始终采取使「吃掉所有牌所需的总操作次数」的期望值最小的行动。在此情况下，总操作次数恰好为 $K$ 的概率是多少？请输出它对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入读入：

• $N$ $K$

输出格式

输出答案。

数据范围

• 所有输入值均为整数。
• $1 \le N \le 5 \times 10^5$
• $N \le K \le 10^9$

3 4

499122177

对于此输入，$N=3$。按牌的排列顺序称它们为 $a,b,c$。下面给出你以使总操作次数期望值最小的方式行动时的一个行动示例。

• 首先，翻开 $a$。
  • 如果 $a$ 上写的是 $1$，吃掉这张牌。
    • 接着，翻开 $b$。
      • 如果 $b$ 上写的是 $2$，吃掉这张牌。
        • 接着，翻开 $c$；因为上面必定是 $3$，吃掉它。此情况下，你用三次操作吃完了所有牌，这种情况发生的概率是 $1/6$。
      • 如果 $b$ 上写的是 $3$，将这张牌翻回背面朝上。
        • 接着，翻开 $c$；因为上面必定是 $2$，吃掉它。之后，翻开 $b$ 并吃掉它。此情况下，你用四次操作吃完了所有牌，这种情况发生的概率是 $1/6$。
  • 如果 $a$ 上写的是 $2$，将这张牌翻回背面朝上。
    • 接着，翻开 $b$。
      • 如果 $b$ 上写的是 $1$，吃掉这张牌。
        • 接着，翻开 $a$ 并吃掉它。接着，翻开 $c$；因为上面必定是 $3$，吃掉它。此情况下，你用四次操作吃完了所有牌，这种情况发生的概率是 $1/6$。
      • 如果 $b$ 上写的是 $3$，将这张牌翻回背面朝上。
        • 此时，每张牌上写的整数都已经明确。于是进行三次操作，按数字顺序吃掉所有牌。此情况下，你用五次操作吃完了所有牌，这种情况发生的概率是 $1/6$。
  • 如果 $a$ 上写的是 $3$，将这张牌翻回背面朝上。
    • 接着，翻开 $b$。
      • 如果 $b$ 上写的是 $1$，吃掉这张牌。
        • 接着，翻开 $c$；因为上面必定是 $2$，吃掉它。之后，翻开 $a$ 并吃掉它。此情况下，你用四次操作吃完了所有牌，这种情况发生的概率是 $1/6$。
      • 如果 $b$ 上写的是 $2$，将这张牌翻回背面朝上。
        • 此时，每张牌上写的整数都已经明确。于是进行三次操作，按数字顺序吃掉所有牌。此情况下，你用五次操作吃完了所有牌，这种情况发生的概率是 $1/6$。

综合以上所有情况，总操作次数为 $3$ 的概率是 $1/6$，为 $4$ 的概率是 $1/2$，为 $5$ 的概率是 $1/3$。对于此样例，输出 $1/2$ 在模 $998244353$ 意义下的表示，即 $499122177$。

3 6

0

500000 777777

251612105

补充说明

对 $998244353$ 取模的概率的定义

可以证明，所求的概率总是一个有理数。此外，在本题的约束下还可以证明，当把所求有理数表示为既约分数 $\frac{P}{Q}$ 时，有 $Q {{}\not\equiv{}} 0 \pmod{998244353}$。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353$。请输出这个 $R$。

• 来源：AtCoder ABC 473 G

子任务设置

• 子任务 1（30 分）：$N \le 20$。
• 子任务 2（30 分）：$N \le 2000$。
• 子任务 3（40 分）：无特殊限制。