题目描述
现在有n(≥3)个白色的球串成了一个圆环,编号依次为1,2,⋯,n,现在你需要把这些球都染黑,具体操作为:
- 等概率随机地选择一个之前从未选过的球(白球、黑球都可以)。
- 将该白球和它相邻的两个白球都染黑。
- 如果所有白球都染黑,那么结束。
求出染黑所有白球的期望步数,答案对998244353取模。
输入格式
从标准输入读入数据。
一行一个正整数n,表示白球的个数。
输出格式
输出到标准输出。
一行一个数字,表示期望步数,对998244353取模。
样例
输入
4
输出
2
样例解释
第一次操作后,只剩下一个白球。接下来,有两个黑球可以选择,一个白球可以选择,不管选哪一个都会染黑所有的球。
样例
输入
5
输出
499122179
解释
数据范围
对于40%的数据,n≤10。
对于100%的数据,n≤5000。