Dice Palindrome :
Difficulty Level : Medium
Submissions : 73
Asked In :
Marks :10
: 1 | : 0
A dice is thrown $$$n$$$ times and the outcomes are used to form a $$$n$$$ digit number in the same order they are thrown. Find the probability that the number thus formed is a palindrome. Each throw can result in 1 to 6.
It can be shown that this can be represented as $$$\frac{P}{Q}$$$, where P and Q are coprime integers, and $$$Q\not\equiv 0$$$ $$$(mod$$$ $$$998244353)$$$. Print the value of $$$P·Q^{-1}$$$ modulo $$$998244353.$$$
$$$\textbf{Constraint}$$$
$$$1$$$ $$$\le$$$ $$$n$$$ $$$\le$$$ $$$10^{5}$$$
Input
The first line contains an integer $$$n$$$, the number of times the dice is thrown.
Output
Print a single integer, the answer to the problem.
Example
Input
3
Output
166374059
