Problem A
Anti-Diagonal Game
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.
Explanation of Sample Input 1
The three strings $S$ such that Alice wins the game are AAA, AAB, and BAA.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 |
3 |
