You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

数字游戏

题目背景

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

样例输入 #1

3

样例输出 #1

665496236

提示

对于 $100\%$ 的数据，$1 \le n\le 10^{18}$。