← 返回题目列表

AtCoder · fps_24_f

F. 彩色纸

中文机器翻译题面 查看原题

分数: 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