数据说明

本题有附加文件（大样例）。

题目描述

邪恶的 $J$ 再磕瓜子，他总共有 $N$ 里瓜子，堆放在一起。他每次都会从这堆瓜子中挑出一粒，吃完一粒瓜子会得到两片瓜子壳，瓜子壳也会被他丢入瓜子堆中。

如果他拿到了之前吃剩下的瓜子壳，他就会把瓜子壳丢掉。否则就会吃掉拿到的瓜子，然后把瓜子壳丢进去。

现在假设邪恶的 $J$ 拿到瓜子堆中的每一粒瓜子或瓜子壳的概率是均等的，问期望多少次能把瓜子拿完。

输入格式

一行，一个正整数 $N$ 。

输出格式

一行，一个整数表示期望次数对 $998244353$ 取模的结果。如果答案可以被表示为分数 $\frac{p}{q}$ ，其中 $p,q$ 互质，那么输出一个数字 $x$ ，满足 $xq \equiv p \pmod{998244353}$

样例

2

3

样例1解释

$N = 2$ 时，邪恶的 $J$ 第一次拿到的肯定是瓜子，然后现在瓜子堆里有 $1$ 粒瓜子和 $2$ 片瓜子壳。接下来他有 $\frac{1}{3}$ 的概率第一次就拿到瓜子，有 $\frac{2}{3} \times \frac{1}{2}$ 的概率在第二次拿到瓜子，有 $\frac{2}{3} \times \frac{1}{2}$ 的概率第三次拿到瓜子。所以期望的次数为 $2 \times \frac{1}{3} + 3 \times \frac{1}{3} + 4 \times \frac{1}{3} = 3$ 。

数据范围与约定

• 对于 $10 \%$ 的数据，满足 $N \le 10$ 。
• 对于 $50 \%$ 的数据，满足 $N \le 500$ 。
• 对于 $100 \%$ 的数据，满足 $N \le 2 \times 10^3$ 。