〈 TREEのOI 2022 Spring 〉Absolutely Simple Game

题目背景

rin 和 len 在玩一个绝对简单的游戏,pcq 为裁判。

题目描述

初始时给定范围 $[l,r]=[1,n]$,pcq 从中均匀随机选出一个自然数 $t$,之后 rin 和 len 两人轮流进行操作,rin 先行。 每次操作方猜测一个整数 $x\in[l,r]$,若 $x=t$,则游戏结束,该方负;若 $x<t$,则调整范围 $[l,r]$ 为 $[x+1,r]$;若 $x>t$,则调整范围 $[l,r]$ 为 $[l,x-1]$。 rin 和 len 两人均充分了解规则且无比可爱聪明(都会最大化自己的胜率),过程中谁都知道场上除了 $t$ 以外的一切信息,求 rin 的胜率。

输入输出格式

输入格式


一行一个整数 $n$。

输出格式


一行一个整数,表示 rin 的胜率,按分数 $\bmod~998244353$ 输出。

输入输出样例

输入样例 #1

3

输出样例 #1

665496236

说明

**样例解释1:** rin 的胜率为 $\dfrac 23$(一开始猜 $2$),$\bmod~998244353$ 后输出为 $665496236$。 *** **本题采用 SubTask 捆绑测试。** | SubTask 编号 | 分值 | 特殊限制 | | :-----------: | :-----------: | :-----------: | | $0$ | $10$ | $n\equiv 0\ \pmod 2$ | | $1$ | $20$ | $n\le 100$ | | $2$ | $30$ | $n\le 10^9$ | |$3$|$40$|$n\le 10^{18}$| 对于 $100\%$ 的数据,$1 \le n\le 10^{18}$。 --- **如何对有理数取模?** $\dfrac {x}{y} \bmod m$ 定义为 $xy^{m-2}\bmod~m$。 $m$ 必须为质数。 保证答案约分后分母不为 $998244353$ 的倍数。