{"problem":{"name":"Colored Paper","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"fps_24_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ sheets of paper, numbered from $1$ to $N$.  \nEach sheet can be painted in one of three colors: red, blue, or yellow.  \nThe coloring must satisfy the following conditions:\n\n*   Each sheet must be painted in exactly one color.\n*   The number of sheets painted blue must be even.\n*   The number of sheets painted yellow must be odd.\n\nFind the number of valid colorings that satisfy the conditions, and output the result modulo $998244353$.\nTwo colorings are considered different if there exists at least one sheet that is painted in different colors.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^9$\n*   $N$ is an integer\n\n## Input\n\nThe input is given from standard input in the following format:\n\n$N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"fps_24_f","tags":[],"sample_group":[["3","7\n\nThere are $7$ valid colorings.  \nHere, $(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$.\n\n*   (red, red, yellow)\n*   (red, yellow, red)\n*   (yellow, red, red)\n*   (blue, blue, yellow)\n*   (blue, yellow, blue)\n*   (yellow, blue, blue)\n*   (yellow, yellow, yellow)"],["1000000000","224965629"]],"created_at":"2026-03-03 11:01:14"}}