CSG-CPC
Online Judge

1238 : 借口

         Time Limit: 2 Sec     Memory Limit: 512 Mb     Submitted: 4     Solved: 3    

Description

【题目背景】

小兰把事情搞砸了。为了应对小艾对 TA 的质询,小兰不得不提前编织一些借口。

【题目描述】

小兰按照如下方式准备了 \(n\) 个借口:小兰开始不断抛掷一枚公平硬币,直到得到反面朝上的结果,设小艾在这之前得到了 \(x\) 次正面,那么 TA 就得到了一个应对第 \(x\) 个问题的借口。注意,对于每次准备借口,正面的次数都重新计数。

接下来小艾按照问题 \(0,1,2\dots\) 的顺序不断质询小兰,如果小兰对该问题有一个借口,那么可以在这个问题上萌混过关,直到轮到一个小兰没有编出借口的问题。

小兰想知道 TA 期望能总共萌混过关多少个问题。小兰自然是只用 \(1\) 微秒就算出了期望的精确数值,现在他们想让你帮忙验算。由于期望的分子和分母可能很大,你只需要输出它对 \(998244353\) 取模的结果。

Input

输入一行一个正整数 \(n\)\(1\leq n\leq 10^5\))。

Output

输出一个数,表示答案对 \(998244353\) 取模的结果。

Sample

1

##CASE##
3
499122177

##CASE##
561512450

Hint

【样例解释 #0】

\(1/2\) 的概率,小兰编出了问题 0 的借口,否则小兰无法萌混过关任何问题。因此期望是 \(1/2 \equiv 499122177 \pmod {998244353}\)

【样例解释 #1】

这是 \(23/16\)

Author

THU