#6358. 前夕

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Sdchr

题目描述

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

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

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

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

输入格式

第一行,一个正数 n

输出格式

输出一行,表示答案。

样例

样例输入

2

样例输出

11

数据范围与提示

对于所有数据, 1 \le n \le {10} ^ 7

子任务 分值 n
1 10 n \le 3
2 n \le 10
3 20 n \le 1000
4 30 n \le {10} ^ 5
5 n \le {10} ^ 7