题目内容

某团队有 $2^m$ 个候选方案参与逐轮两两对比淘汰评审，方案编号依次为 $1$ 到 $2^m$。每个方案的优先级评分即为其编号（评分越高的方案越优）。在任一轮对比中，若编号为 $i$ 的方案与编号为 $j$ 的方案被分到一起，则方案 $i$ 胜出的概率为：

具体评审流程如下：

• 首轮，所有方案按初始编排顺序两两配对：位置 $1$ 的方案与位置 $2$ 的方案对比，位置 $3$ 的方案与位置 $4$ 的方案对比，……，位置 $2^m-1$ 的方案与位置 $2^m$ 的方案对比。（注意：位置 $1$ 上的方案编号不一定是 $1$）
• 后续各轮，将上一轮胜出的方案按胜出先后排成一行，再次依次每两个配对（位置 $1$ 与 $2$ 对比，位置 $3$ 与 $4$ 对比，……），胜者进入下一轮，直至产生唯一胜者。

初始编排是一个长度为 $2^m$ 的排列，每个方案恰好出现一次，且顺序决定首轮配对关系。请计算：共有多少种不同的初始编排顺序，能使编号为 $1$ 的方案最终胜出的概率达到最大值。答案请对 $998244353$ 取模后输出。

【名词解释】

长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数按任意顺序组成的数组，每个整数恰好出现一次。例如，$\{3,1,4,2\}$ 是一个长度为 $4$ 的排列，而 $\{2,3,2,4\}$ 和 $\{1,5,3,2\}$ 都不是排列——前者存在重复元素 $2$，后者包含超出范围的数 $5$。

输入描述

读入一行一个整数 $m$（$1 \le m \le 12$）。

输出描述

输出一行一个非负整数，表示答案对 $998244353$ 取模后的结果。

样例1

输入

2

输出

8

说明

$m=2$ 时共有 $2^2=4$ 个方案（编号 $1\sim 4$），全部 $4!=24$ 种编排。考察一种使方案 $1$ 胜出概率最大的典型编排 $\{1,2,3,4\}$：

• 首轮：方案 $1$ 与方案 $2$ 对比，胜出概率 $\frac{1}{1+2}=\frac{1}{3}$。
• 首轮另一组：方案 $3$ 与方案 $4$ 对比，$3$ 胜出概率 $\frac{3}{3+4}=\frac{3}{7}$，$4$ 胜出概率 $\frac{4}{7}$。
• 终轮：方案 $1$ 若对 $3$，胜出概率 $\frac{1}{1+3}=\frac{1}{4}$；若对 $4$，胜出概率 $\frac{1}{1+4}=\frac{1}{5}$。
• 综合概率：$\frac{1}{3}\times\left(\frac{3}{7}\times\frac{1}{4}+\frac{4}{7}\times\frac{1}{5}\right)=\frac{31}{420}\approx 0.0738$。

该概率即为所有编排中方案 $1$ 胜出的最大可能值。经枚举验证，恰有 $8$ 种不同的初始编排可达该上界，故输出 $8$。

样例2

输入

3

输出

128