QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
Statistics

题目描述

现在有$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$。