题目描述

现在有$n(\geq 3)$个白色的球串成了一个圆环，编号依次为$1,2,\cdots,n$，现在你需要把这些球都染黑，具体操作为：

1. 等概率随机地选择一个之前从未选过的球（白球、黑球都可以）。
2. 将该白球和它相邻的两个白球都染黑。
3. 如果所有白球都染黑，那么结束。

求出染黑所有白球的期望步数，答案对998244353取模。

输入格式

从标准输入读入数据。

一行一个正整数$n$，表示白球的个数。

输出格式

输出到标准输出。

一行一个数字，表示期望步数，对998244353取模。

样例

输入

4

输出

2

样例解释

第一次操作后，只剩下一个白球。接下来，有两个黑球可以选择，一个白球可以选择，不管选哪一个都会染黑所有的球。

样例

输入

5

输出

499122179

解释

数据范围

对于$40\%$的数据，$n\leq 10$。

对于$100\%$的数据，$n\leq 5000$。