题目内容

在一场单败淘汰赛中，共有 $N = 2^m$ 名选手参加。他们的能力值恰好是 $1$ 到 $N$ 的每一个整数，没有重复。比赛采用固定的淘汰规则：

1. 首先，将所有选手按照某种初始顺序排成一行。
2. 每一轮，将当前序列中相邻的两人配对对战：第 $1$ 名对第 $2$ 名，第 $3$ 名对第 $4$ 名，以此类推。
3. 若能力值为 $x$ 的选手与能力值为 $y$ 的选手对战，则 $x$ 获胜的概率为 $\frac{x}{x+y}$。
4. 每轮结束后，胜者保持原有相对顺序，形成新的序列，继续下一轮，直至产生唯一的冠军。

现在，你希望能力值为 $1$ 的选手获得最终冠军的概率尽可能大。请问：在所有可能的初始排列中，有多少种排列方式可以使得能力值为 $1$ 的选手的夺冠概率达到最大值？答案请对 $998244353$ 取模。

数据范围：$m$ 满足 $1 \le m \le 12$。

输入描述

输入包含一行一个整数 $m$（$1 \le m \le 12$），表示选手总数为 $2^m$。

输出描述

输出一行一个整数，表示满足条件的初始排列数量对 $998244353$ 取模后的结果。

样例1

输入

1

输出

2

说明

当 $m=1$ 时，总选手数 $N=2^1=2$，能力值为 1 和 2。无论怎样排列，能力值为 1 的选手夺冠概率均为 $\frac{1}{1+2}=\frac{1}{3}$，即所有 $2! = 2$ 种排列都能使夺冠概率达到最大值。因此答案为 2。

样例2

输入

3

输出

128

说明

总选手数 $N=2^3=8$。要使能力值为 1 的选手夺冠概率最大，必须使其在每一轮中对阵的对手尽可能弱。可以证明，满足条件的初始排列总数为 $2^{N-1}=2^7=128$。对 $998244353$ 取模后仍为 128。

样例3

输入

4

输出

32768

说明

总选手数 $N=2^4=16$。同理，最优排列数量为 $2^{N-1}=2^{15}=32768$，取模后结果为 32768。