Excuse
给你一枚公平硬币:每次投掷正面和反面的概率均为 50%。你要用它生成一个含 n 个整数的序列 a1,a2,…,an,重复下面的过程恰好 n 次:
- 不断投掷硬币,直到第一次出现反面。
- 设停止前出现了 k 次正面,将整数 k 添加到序列末尾。
对整数序列 b1,…,bm,定义 mex(b1,…,bm) 为其中没有出现的最小非负整数。等价地,答案 x 没有出现,而比 x 小的所有非负整数均已出现。例如:
mex(0,1,0,3)=2,
mex(4,3,2,1,0,6,7,5)=8,
mex(1,2,3)=0.
求 mex(a1,…,an) 的期望,对 998244353 取模。
输入格式
输入只有一行,包含整数 n(1≤n≤105)。
输出格式
输出一行一个整数,表示所求期望对 998244353 取模的结果。
原样例 1
1
499122177
原样例 2
3
561512450
原样例说明
第一个样例中:若 a1=0,则 mex 为 1,这件事发生的概率为 1/2;否则 mex 为 0。因此期望为
$$1\times\frac12+0\times\left(1-\frac12\right)=\frac12\equiv499122177\pmod{998244353}.$$