Ilie has a magical machine that can generate messages from binary strings.

First, Ilie gives the machine a binary string $s$ of length $n$. The machine can then generate a message by deleting any number of characters from $s$ (possibly none), without changing the order of the remaining characters.

For example, if $s = \texttt{010}$, the machine can generate the messages $\texttt{0}$, $\texttt{1}$, $\texttt{01}$, $\texttt{10}$, and several others.

The machine can also delete all characters, generating an empty message.

Ilie is only interested in distinct messages. If the same message can be generated in multiple ways, it is counted only once.

Ilie wants to choose a binary string of length $n$ so that his machine can generate as many distinct messages as possible.

Help Ilie find the maximum possible number of distinct messages he can generate!

Since the answer can be very large, print it modulo $998244353$.

Input

The only line contains a single integer $n$ ($1 \le n \le 10^6$).

Output

Print a single integer: the maximum possible number of distinct messages Ilie can generate, modulo $998244353$.

Example

stdin

3

stdout

7

Note

The table below lists every binary string of length $3$ together with all the distinct messages it can generate. Here, $\varepsilon$ denotes the empty message.

Therefore, the maximum possible number of distinct messages is $7$.