题目描述

为了抵御以尼古拉·奥尔丁为首的上古龙族的入侵，地球的守护者 Yopilla 集齐了 $n$ 种人类文明的本源力量——世界之力。

Yopilla 打算使用若干种技能来对抗尼古拉·奥尔丁的进攻。每种技能由若干种世界之力构成：具体来说，以世界之力为元素的每个子集都对应一种技能，因此一共有 $2^n$ 种不同的技能。Yopilla 可以选择任意非空的技能集合（也可以选择不使用任何技能）来参与战斗。

大战前夕，Yopilla 走在波士顿的街头，天空中飞过的 4 只白鸽让他洞察了胜利的秘密：当且仅当他使用的所有技能中，都含有的世界之力的种类数（即所有选中技能的交集大小）恰好为 4 的倍数时，他才能打败敌人。

请你计算 Yopilla 有多少种符合条件的技能使用情况，答案需对 998244353 取模。

输入格式

第一行输入一个正整数 $n$，表示世界之力的种类数。

输出格式

输出一行一个整数，表示符合条件的技能使用情况数对 998244353 取模的结果。

样例

输入

2

输出

11

样例说明

当 $n=2$ 时，所有技能（子集）为 $\emptyset, \{1\}, \{2\}, \{1,2\}$，共 $4$ 种。符合条件的情况包含：

1. 不使用任何技能（交集为空集，大小 0 是 4 的倍数）；
2. 仅使用 $\emptyset$（交集为 $\emptyset$，大小 0）；
3. 仅使用 $\{1\}$（交集为 $\{1\}$，大小 1 不符合，排除）；
4. 仅使用 $\{2\}$（交集为 $\{2\}$，大小 1 不符合，排除）；
5. 仅使用 $\{1,2\}$（交集为 $\{1,2\}$，大小 2 不符合，排除）；
6. 使用 $\{1\}$ 和 $\{2\}$（交集为 $\emptyset$，大小 0）；
7. 使用 $\{1\}$ 和 $\{1,2\}$（交集为 $\{1\}$，大小 1 不符合，排除）；
8. 使用 $\{2\}$ 和 $\{1,2\}$（交集为 $\{2\}$，大小 1 不符合，排除）；
9. 使用 $\{1\}, \{2\}$ 和 $\{1,2\}$（交集为 $\emptyset$，大小 0）；
10. 使用 $\emptyset$ 和任意其他技能组合（只要最终交集大小为 4 的倍数）。

经统计，符合条件的情况共计 11 种，与样例输出一致。

数据范围与提示

通用数据限制

$1 \le n \le 10^7$

子任务划分

关键提示

本题核心是集合计数问题，需围绕“子集族交集大小”的约束展开。由于 $n$ 规模极大（可达 $10^7$），无法直接枚举所有子集，需结合容斥原理和组合数学推导公式，通过预处理快速幂、组合数等实现高效计算。空集的交集定义为全集，但本题中“不使用任何技能”或“仅使用空集”的情况需单独对应交集大小为 0 的场景（0 是 4 的倍数）。