International Olympiad in Fishing - Problème

第一届国际钓鱼奥林匹克（“IOF”）计划今年在亚特兰蒂斯举办。来自世界各地的最优秀的鱼将争夺世界鱼类冠军的称号。

小蓝鱼（Little Cyan Fish）准备参加这场锦标赛。比赛的主席小果冻鱼（Little Gelly Fish）告诉了他今年比赛的规则：将使用一款名为“Balatro”的卡牌游戏来决定胜负。

游戏中有 $n$ 张卡牌，用 $1$ 到 $n$ 的整数进行编号。每张卡牌有两个附加属性：点数（rank）和花色（suit）。点数和花色都是在 $[1, n]$ 范围内独立且均匀随机选择的整数，两张不同的卡牌可能具有相同的点数或花色。

每张卡牌的编号写在卡牌的背面，而点数和花色写在正面。目前，所有卡牌都按编号升序排列放在桌面上，背面朝上。因此，玩家知道所有卡牌的编号，但看不到每张卡牌的点数或花色。

桌面上还有两个分别标记为“Rank”和“Suit”的按钮。小果冻鱼告诉小蓝鱼，他可以操作这两个按钮，规则如下：

小果冻鱼指出，排序过程是稳定的。这意味着，在按下其中一个按钮后，对于任意两张卡牌，如果它们对应的属性（取决于按下的按钮，即点数或花色）不同，则属性值较小的卡牌将在排序后的顺序中靠前出现。如果它们对应的属性相同，则它们的相对顺序将保持不变。

“你可以多次按下按钮，”小果冻鱼说，“然后……你必须告诉我每张卡牌的具体点数和花色。”

小蓝鱼想知道，在最优策略下，正确猜出所有卡牌的点数和花色的概率是多少。由于小果冻鱼生活在 $\mathbb{F}_{998\,244\,353}$ 的世界中，你只需要给出答案模 $998\,244\,353$ 的结果。

输入的第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)。

输出单行，包含一个整数，表示答案模 $998\,244\,353$ 的结果。

686292993

301495273

126716306

在第一个样例中，有两张卡牌。在此样例的限制下，小蓝鱼可以采取以下策略：

首先，小蓝鱼会按下一次“Rank”按钮，以检查这两张卡牌是否被交换，然后按下一次“Suit”按钮，以检查这两张卡牌是否被交换。

让我们考虑所有可能的结果：

如果“Rank”按钮和“Suit”按钮都导致卡牌交换，小蓝鱼将按如下方式猜测：
- 第一张卡牌的点数为 2，花色为 1。
- 第二张卡牌的点数为 1，花色为 2。
如果“Rank”按钮导致交换，但“Suit”按钮没有，小蓝鱼将按如下方式猜测：
- 第一张卡牌的点数为 2，花色为 2。
- 第二张卡牌的点数为 1，花色为 1。
如果“Rank”按钮和“Suit”按钮都没有导致交换，小蓝鱼将按如下方式猜测：
- 第一张卡牌的点数为 1，花色为 1。
- 第二张卡牌的点数为 2，花色为 2。
如果“Rank”按钮没有导致交换，但“Suit”按钮导致了交换，小蓝鱼将再次按下“Rank”按钮：
- 如果在第二次按下“Rank”按钮后发生了交换，小蓝鱼将按如下方式猜测：
  - 第一张卡牌的点数为 1，花色为 2。
  - 第二张卡牌的点数为 2，花色为 1。
- 如果在第二次按下“Rank”按钮后没有发生交换，小蓝鱼将按如下方式猜测：
  - 第一张卡牌的点数为 1，花色为 2。
  - 第二张卡牌的点数为 1，花色为 1。

可以证明，通过上述策略，小蓝鱼正确猜出所有点数和花色的概率为 $\frac{5}{16} \equiv 686\,292\,993 \pmod{998\,244\,353}$，且这在所有策略中是最优的。

QOJ.ac