I. Julienne the Deck
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Daniel is trying to shuffle his deck of $$$n$$$ distinct cards. To do this, he has created a new shuffle operation which he calls 'Julienning' the deck.

First he chooses an integer $$$i$$$, $$$1 \leq i \lt n$$$. He then simultaneously reverses the first $$$i$$$ cards of the deck, and the last $$$n - i$$$ cards of the deck.

For example, if his deck is initially in the permutation $$$p = [1, 4, 3, 2, 5, 6]$$$, then after a Julienne operation with $$$i = 4$$$ his deck becomes $$$p' = [2, 3, 4, 1, 6, 5]$$$.

If Daniel starts with a sorted deck of $$$n$$$ cards, how many permutations of his deck can he achieve using any number (possibly zero) of Julienne operations?

As the answer may be large, output the value modulo $$$998244353$$$.

Input

The first line of input consists of single integer n $$$(1 \leq n \leq 10^{12})$$$ — the number of cards in the deck.

Output

Output a single integer — the number of achievable permutations, modulo $$$998244353$$$.

Examples
Input
1
Output
1
Input
1000000000000
Output
516560941
Input
3
Output
6