AT_fps_24_f 色紙

题目描述

有 $N$ 张纸，编号从 $1$ 到 $N$。
每张纸可以涂成三种颜色中的一种：红色、蓝色或黄色。
涂色方案需要满足以下条件：

• 每张纸只能被涂成一种颜色。
• 被涂成蓝色的纸的数量必须是偶数。
• 被涂成黄色的纸的数量必须是奇数。

求满足上述条件的涂色方案总数，并输出对 $998244353$ 取模后的结果。

当存在至少一张纸涂色不同，则两种涂色方案视为不同。

输入格式

输入由标准输入给出，格式如下：

$N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3

输出 #1

7

输入输出样例 #2

输入 #2

1000000000

输出 #2

224965629

说明/提示

样例解释 1

共有 $7$ 种合法的涂色方案。
其中，$(c_1, c_2, c_3)$ 表示第 $1$ 张纸涂成 $c_1$，第 $2$ 张纸为 $c_2$，第 $3$ 张纸为 $c_3$。

• (红色, 红色, 黄色)
• (红色, 黄色, 红色)
• (黄色, 红色, 红色)
• (蓝色, 蓝色, 黄色)
• (蓝色, 黄色, 蓝色)
• (黄色, 蓝色, 蓝色)
• (黄色, 黄色, 黄色)

数据范围

• $1 \leq N \leq 10^9$
• $N$ 为整数

由 ChatGPT 5 翻译