D. Gray Distances
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's define a sequence of Gray Codes $$$G_n$$$ as follows:

  • if $$$n = 0$$$ then $$$G_n$$$ = {0},
  • if $$$n \gt 0$$$ then $$$G_{n}$$$ is equal to $$$G_{n - 1} \cdot R(G_{n - 1} + 2^{n-1})$$$, where $$$\cdot$$$ means the concatenation of sequences, $$$R(s)$$$ means the reverse of sequence $$$s$$$ and $$$s + c$$$ means sequence $$$s$$$ with every number increased by a constant $$$c$$$.
For example, $$$G_1 = \{0, 1\}$$$, $$$G_2 = \{0, 1, 3, 2\}$$$ and $$$G_3 = \{0, 1, 3, 2, 6, 7, 5, 4\}$$$. For a Gray Code $$$G_n$$$, we define a $$$n \times 2^n$$$ table $$$T_n$$$. The cell in the $$$i$$$-th row and $$$j$$$-th column of $$$T_n$$$ is equal to the $$$i$$$-th least significant bit of the $$$j$$$-th number in the sequence $$$G_n$$$.
01100110
00111100
00001111

The table $$$T_3$$$

Two cells in the table are adjacent if they share a side. The distance between cells $$$(a, b)$$$ and $$$(c, d)$$$, satisfying $$$T_n(a, b) = T_n(c, d) = 1$$$, is defined as the minimal number of moves needed to get from one cell to the other moving only on cells that are $$$1$$$'s. Given $$$n$$$, your task is to calculate the sum of distances between every ordered pair of cells modulo 998 244 353.

Input

The first line of input contains one integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$).

Output

Print one line containing the answer.

Example
Input
2
Output
20