AT_fps_24_f 色紙

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.

The input is given from standard input in the following format: > $ N $

Print the answer.

### Sample Explanation 1 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) ### Constraints - $ 1 \leq N \leq 10^9 $ - $ N $ is an integer