#P18526. Excuse

Excuse

Excuse

给你一枚公平硬币:每次投掷正面和反面的概率均为 50%50\%。你要用它生成一个含 nn 个整数的序列 a1,a2,…,ana_1,a_2,\ldots,a_n,重复下面的过程恰好 nn 次:

  • 不断投掷硬币,直到第一次出现反面。
  • 设停止前出现了 kk 次正面,将整数 kk 添加到序列末尾。

对整数序列 b1,…,bmb_1,\ldots,b_m,定义 mex⁡(b1,…,bm)\operatorname{mex}(b_1,\ldots,b_m) 为其中没有出现的最小非负整数。等价地,答案 xx 没有出现,而比 xx 小的所有非负整数均已出现。例如:

mex⁡(0,1,0,3)=2,\operatorname{mex}(0,1,0,3)=2, mex⁡(4,3,2,1,0,6,7,5)=8,\operatorname{mex}(4,3,2,1,0,6,7,5)=8, mex⁡(1,2,3)=0.\operatorname{mex}(1,2,3)=0.

求 mex⁡(a1,…,an)\operatorname{mex}(a_1,\ldots,a_n) 的期望,对 998 244 353998\,244\,353 取模。

输入格式

输入只有一行,包含整数 nn(1≤n≤1051\le n\le10^5)。

输出格式

输出一行一个整数,表示所求期望对 998 244 353998\,244\,353 取模的结果。

原样例 1

1
499122177

原样例 2

3
561512450

原样例说明

第一个样例中:若 a1=0a_1=0,则 mex 为 1,这件事发生的概率为 1/21/2;否则 mex 为 0。因此期望为

$$1\times\frac12+0\times\left(1-\frac12\right)=\frac12\equiv499122177\pmod{998244353}.$$