分数: 3 点
问题陈述
有 N 张纸,编号为 1 to N.
每张纸都可以涂成三种颜色之一:红色、蓝色或黄色。
着色必须满足以下条件:
- 每张纸都必须涂成一种颜色。
- 涂成蓝色的纸张数量必须是偶数。
- 涂成黄色的张数必须是奇数。
求满足条件的有效着色数,并输出结果模 998244353.
如果存在至少一张涂有不同颜色的纸张,则认为两种颜色不同。
约束
- 1 \leq N \leq 10^9
- N 是一个整数
输入
输入由标准输入给出,格式如下:
N
输出
打印答案。
示例输入 1
3
示例输出 1
7
有 7 有效着色。
在这里, (c_1, c_2, c_3) 表示该表 1 涂有颜色 c_1,表 2 in c_2和表 3 in c_3.
- (红、红、黄)
- (红、黄、红)
- (黄、红、红)
- (蓝色,蓝色,黄色)
- (蓝色、黄色、蓝色)
- (黄、蓝、蓝)
- (黄、黄、黄)
示例输入 2
1000000000
示例输出 2
224965629