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$$$.