UOJ Logo Universal Online Judge

UOJ

#702. 张飞卷精兵

附件下载 统计

新年来了,张飞决定开启一场内卷大赛,胜者将得到十全大补 skip 蚤汤一碗!

张飞手下有 $2^n$ 名精兵来参赛,每名精兵都有一个内卷值。惊人的是,精兵与精兵之间的差距十分巨大!具体来说,第 $i$ 名精兵的卷力是 $2^{i-1}$($i\in [1,2^n]$)。注意,精兵中最高的卷力达到了 $2^{2^n-1}$。

两名精兵如果展开内卷大比拼,他们的卷力将以相同速度被消耗直到一人的卷力被消耗殆尽。具体来说,卷力为 $a$ 的精兵和卷力为 $b$ 的精兵比拼后(不妨设 $a>b$),第一名精兵将会获胜,并且它的卷力会变成 $a-b$。而输掉比拼的精兵将会出局。可以证明,无论怎样比拼,都不会出现平局的情况。

大赛的赛制是单淘汰赛,具体的,比赛将进行 $n$ 轮,第 $i$ 轮中 $(i\in [1,n])$:

  1. 将未出局的 $2^{n-i+1}$ 名精兵分成 $2^{n-i}$ 对。
  2. 让每一对精兵内卷大比拼,败者出局,胜者进入下一轮。

最后留下的精兵就是大赢家。

张飞身经百战,一眼看透了最后的赢家。不过张飞希望让他的获胜之路更紧张刺激,所以张飞想让聪明的你安排比赛顺序,使得最后的赢家剩余卷力尽可能小。你只需要输出这个最小值对 $998244353$ 取模后的结果。

输入格式

一行一个整数 $n$ 表示参赛选手数是 $2^n$。

输出格式

一行一个整数表示最后胜者卷力的最小值对 $998244353$ 取模后的结果。

样例一

input

2

output

3

explanation

精兵的初始卷力分别为 $1,2,4,8$。

比赛将进行两轮。第一轮:$(2,8)\rightarrow 6,(1,4)\rightarrow 3$,第二轮:$(6,3)\rightarrow 3$。可以证明这是大赢家卷力值的最小可能。

样例二

input

98

output

992994918

数据范围与提示

子任务编号 $n\leq$ 分值
$1$ $4$ $10$
$2$ $20$ $25$
$2$ $1000$ $25$
$3$ $10^6$ $40$

对于所有数据,保证 $1\leq n\leq 10^6$。

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$