该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

翻牌谜题

题目背景

在《赛尔号》游戏的某个活动中，只有集齐三个指定道具才能获得精灵“六界御神”，而第三个道具则需要完成以下小游戏。

题目描述

初始情况下，场上一共有 $n$ 张背面朝上的牌。

玩家可以尝试挑战 Boss，每次挑战成功，都将执行以下操作：

• 等概率随机选择 $k\in \{1,2,3\}$（选到每个数的概率都是 $1/3$）。
• 从所有卡牌中等概率随机选择不同的 $k$ 张牌（一共 $\binom{n}{k}$ 种选取方式，都是等概率的），将这 $k$ 张牌 翻面 ，即：背面朝上的牌将改为正面朝上，正面朝上的牌将改为背面朝上。

如果某一时刻所有 $n$ 张卡牌都正面朝上，则玩家获得该道具。

假设玩家每次挑战都成功，现在 pzr 想知道，获得道具所需的期望挑战次数是多少？答案对 $998244353$ 取模。

输入格式

第一行一个正整数 $n$。

输出格式

一个非负整数，表示期望值，对 998244353 取模。

样例输入1

3

样例输出1

6

样例输入2

5

样例输出2

249561121

样例 2 解释

期望为 131 / 4，而 $249561121 \times 4 \equiv 131 \pmod {998244353}$，因此输出 249561121。

样例输入3

9

样例输出3

777254234

样例 3 解释

游戏中实际取的是 9 张牌，其中需要挑战的次数期望为 764763 / 1450，约为 527.42 次。

样例输入4

100

样例输出4

687351762

数据范围及约定

对于 $50\%$ 的数据，$3\le n\le 9$。

对于 $90\%$ 的数据，$3\le n\le 500$。

对于 $100\%$ 的数据，$3\le n\le 10^5$。