该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Cube

题目背景

超立方体（Hypercube）是立方体在 $n$ 维空间 中的推广。它在数学（尤其是几何学、组合数学和拓扑学）和计算机科学（如并行计算架构）中非常重要。

超立方体可以通过以下递归方式构建：

$0$ 维超立方体 ($Q⁰$): 是一个点（没有边）。

$1$ 维超立方体 ($Q¹$): 是一条线段。它由两个点和连接它们的一条边组成。

$n$ 维超立方体 ($Qⁿ$) ($n ≥ 2$): 取两个 完全相同的 ($n-1$)维超立方体，然后将它们对应的顶点用新的边连接起来。

几何意义： 想象在 $n$ 维空间中，将一个 ($n-1$) 维超立方体沿着第 $n$ 个坐标轴方向“平移”一个单位距离（从 $0$ 移动到 $1$），并连接原始位置和平移后位置的所有对应顶点。

题目描述

在一个 $n$ 维空间中有一个 $n$ 维的超立方体。

请你求出，从这个超立方体的 $2^n$ 个顶点中选出三个，恰好形成直角三角形的方案数。

我们可以给超立方体的 $2^n$ 个顶点标注 $1∼2^n$ 的标号，两种方案不同当且仅当三个顶点对应标号从小到大排序后得到的三元组不同。

答案对 $998244353$ 取模。

输入格式

一行，输入一个整数 $n$.

输出格式

一行，输出一个整数，表示组成直角三角形的方案数。

答案对 $998244353$ 取模。

输入输出样例 #1

输入 #1

2

输出 #1

4

输入输出样例 #2

输入 #2

3

输出 #2

48

输入输出样例 #3

输入 #3

15

输出 #3

429588246

输入输出样例 #4

输入 #4

65536

输出 #4

573587881

说明/提示

对于 $100\%$ 的数据，保证 $n \le 10^{18}$.