/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 3 点
問題文
1 から N までの番号がついた N 枚の紙があります。紙同士は区別できます。
あなたはそれぞれの紙を赤色・青色・黄色のいずれかの色で塗っていきます。
ただし、塗り方は次の条件を全て満たす必要があります。
- それぞれの紙はちょうど 1 色に塗られる必要がある。
- 青色に塗られた紙の枚数は偶数枚である。
- 黄色に塗られた紙の枚数は奇数枚である。
条件を満たす色の塗り方の個数を 998244353 で割った余りを求めてください。
ただし、2 つの色の塗り方は、塗られた色が異なる紙が存在する時に別々に数えます。
制約
- 1 \leq N \leq 10^9
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
3
出力例 1
7
条件を満たす塗り方は次の 7 通りです。ここで (c_1, c_2, c_3) は、 1 枚目を c_1 色に、2 枚目を c_2 色に、3 枚目を c_3 色に塗ることを意味します。
- (赤, 赤, 黄)
- (赤, 黄, 赤)
- (黄, 赤, 赤)
- (青, 青, 黄)
- (青, 黄, 青)
- (黄, 青, 青)
- (黄, 黄, 黄)
入力例 2
1000000000
出力例 2
224965629
Score: 3 points
Problem Statement
There are N sheets of paper, numbered from 1 to N.
Each sheet can be painted in one of three colors: red, blue, or yellow.
The coloring must satisfy the following conditions:
- Each sheet must be painted in exactly one color.
- The number of sheets painted blue must be even.
- The number of sheets painted yellow must be odd.
Find the number of valid colorings that satisfy the conditions, and output the result modulo 998244353.
Two colorings are considered different if there exists at least one sheet that is painted in different colors.
Constraints
- 1 \leq N \leq 10^9
- N is an integer
Input
The input is given from standard input in the following format:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
7
There are 7 valid colorings.
Here, (c_1, c_2, c_3) means that sheet 1 is painted in color c_1, sheet 2 in c_2, and sheet 3 in c_3.
- (red, red, yellow)
- (red, yellow, red)
- (yellow, red, red)
- (blue, blue, yellow)
- (blue, yellow, blue)
- (yellow, blue, blue)
- (yellow, yellow, yellow)
Sample Input 2
1000000000
Sample Output 2
224965629