新年来了，张飞决定开启一场内卷大赛，胜者将得到十全大补 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)\to 6,(1,4)\to 3$，第二轮：$(6,3)\to 3$。可以证明这是大赢家卷力值的最小可能。

样例二

input

98

output

992994918

数据范围与提示

对于所有数据，保证 $1\le n\le {10}^6$。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{512MB}}$