题目描述

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

Yopilla 打算使用若干种技能来对抗尼古拉奥尔丁的进攻。每种技能由若干种世界之力构成。换句话说，一共有 $2 ^ n$ 种技能，Yopilla 要使用若干种技能来对抗尼古拉奥尔丁。

大战前夕，Yopilla 走在波士顿的街头，突然看见天空中飞过了 $4$ 只白鸽，他便洞察了战胜尼古拉奥尔丁的秘密：只要他使用的技能中，都含有的世界之力的种类数恰好为 $4$ 的倍数，他便可以打败敌人。

Yopilla 想知道，他有多少种使用技能的情况，能战胜敌人。请你替 Yopilla 回答这个问题，答案对 $998244353$ 取模即可。

输入格式

第一行，一个正数 $n$ 。

输出格式

输出一行，表示答案。

2

11

数据范围与提示

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