A. Anti-Diagonal Game
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game!

Alice and Bob both knows some string $$$S$$$ of length $$$N+1$$$ that consists of only the characters A and B. The game is played on a $$$(N+1) \times (N+1)$$$ matrix, with rows and columns numbered from $$$0$$$ to $$$N$$$. We denote the cell in row $$$i$$$ and column $$$j$$$ as $$$(i, j)$$$.

Initially, a token is placed on $$$(0, 0)$$$. Each turn,

  • Suppose the token is on cell $$$(i, j)$$$. The turn player must move the token to either $$$(i+1, j)$$$ or $$$(i, j+1)$$$.

The game ends when the token reaches the anti-diagonal of the matrix, which is the set of cells $$$\{(i, j) \mid i + j = N\}$$$. In other words, there will be a total of $$$N$$$ turns in the game. The winner of the game is determined by the string $$$S$$$:

  • If the token ends on the anti-diagonal cell $$$(i, N - i)$$$, and $$$S_i = \texttt{A}$$$, then Alice wins.
  • If the token ends on the anti-diagonal cell $$$(i, N - i)$$$, and $$$S_i = \texttt{B}$$$, then Bob wins.

Alice moves first. Among the $$$2^{N+1}$$$ possible strings $$$S$$$, how many strings are there such that Alice wins the game, assuming both players play optimally? Since the answer can be very large, output the answer modulo $$$10^9 + 3233$$$.

Input

The input contains a single integer $$$N$$$ ($$$1 \leq N \leq 100\,000$$$).

Output

Output a single integer denoting the number of strings $$$S$$$ such that Alice wins the game, modulo $$$10^9 + 3233$$$, assuming both players play optimally.

Example
Input
2
Output
3
Note

The three strings $$$S$$$ such that Alice wins the game are AAA, AAB, and BAA.