Omkar and Akmar
Contest: Codeforces Round 724 (Div. 2)
Difficulty rating: 2600
Tags: chinese remainder theorem, combinatorics, constructive algorithms, fft, games, geometry, math, meet-in-the-middle, string suffix structures

Omkar and Akmar are playing a game on a circular board with $$$n$$$ ($$$2 \leq n \leq 10^6$$$) cells. The cells are numbered from $$$1$$$ to $$$n$$$ so that for each $$$i$$$ ($$$1 \leq i \leq n-1$$$) cell $$$i$$$ is adjacent to cell $$$i+1$$$ and cell $$$1$$$ is adjacent to cell $$$n$$$. Initially, each cell is empty.

Omkar and Akmar take turns placing either an A or a B on the board, with Akmar going first. The letter must be placed on an empty cell. In addition, the letter cannot be placed adjacent to a cell containing the same letter.

A player loses when it is their turn and there are no more valid moves.

Output the number of possible distinct games where both players play optimally modulo $$$10^9+7$$$. Note that we only consider games where some player has lost and there are no more valid moves.

Two games are considered distinct if the number of turns is different or for some turn, the letter or cell number that the letter is placed on were different.

A move is considered optimal if the move maximizes the player's chance of winning, assuming the other player plays optimally as well. More formally, if the player who has to move has a winning strategy, they have to make a move after which they will still have a winning strategy. If they do not, they can make any move.

Input format:
The only line will contain an integer $$$n$$$ ($$$2 \leq n \leq 10^6$$$) — the number of cells on the board.

Output format:
Output a single integer — the number of possible distinct games where both players play optimally modulo $$$10^9+7$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
For the first sample case, the first player has $$$4$$$ possible moves. No matter what the first player plays, the second player only has $$$1$$$ possible move, so there are $$$4$$$ possible games.

Example input:
2

Example output:
4

Example input:
69420

Example output:
629909355

Editorial:
<spoiler summary="Hint 1">Solve a simpler version of the problem, where you just need to print who would win if both players play optimally.<p><spoiler summary="Hint 1 Hint">Consider the possible ending states of the board.</spoiler> </p></spoiler>
<spoiler summary="Hint 1 Solution">The 2nd player, Omkar, always wins no matter what either player does. The easiest way to see this is by considering ending states of the board. An ending state with an even number of letters means that the 2nd player wins (because the first player is the next player and there are no more moves), and an ending state with an odd number of letters means that the 1st player wins.<p>An ending state must be in the form ABABA... or BABA..., where there are 0 or 1 empty cells in between each letter and the letters form an alternating pattern. If there is more than 1 empty cell in between two cells, then a player will be able to play a letter, thus it is not a valid ending state.</p><p>If an ending state has two of the same letters next to each other, then it is not a valid ending state. Either they are next to each other, which is illegal, or there is at least one empty cell in between them, which means that a player can play the other letter in between. Since the ending state must form an alternating pattern, there must be an even number of states. Thus, the 2nd player, Omkar, always wins. </p></spoiler>
<spoiler summary="Hint 2">Find the implication of the 2nd player always winning on the number of optimal games.</spoiler>
<spoiler summary="Hint 2 Solution">Because the 2nd player always wins no matter what, the number of optimal games basically means the total number of possible games.</spoiler>
<spoiler summary="Solution"> Because of Hint 1 and Hint 2, we want to find the total number of possible games. This can be done by iterating over the number of moves and counting the number of ways to play a game with that number of moves.
We want to find the number of games that end in $$$x$$$ moves on a board of size $$$n$$$.
The first step is to calculate the total number of ending states. If $$$x=n$$$, the total number of ending states is just $$$2$$$ because you can either have ABABA... or BABAB...
Otherwise, a game that ends in $$$x$$$ moves will consist of $$$x$$$ letters, for example A|B|A|B|... where a | is a possible location of a single empty cell (there cannot be multiple empty cells next to each other or else it would not be a valid ending state). There are $$$x$$$ possible places where there can be an empty cell, and $$$n-x$$$ empty cells, so there are $$$\binom x n-x$$$ ways to choose places to put empty cells. Due to the circular nature of the board, you need to account for the case where the first cell on the board is an empty cell (the previous formula only works if the first cell is not empty). If you set the first cell to be empty, there are not $$$x-1$$$ possible places to put an empty cell and $$$n-x-1$$$ remaining empty cells, so you have to add $$$\binom {x-1} {n-x-1}$$$. Multiply the answer by $$$2$$$ to account for starting with an A or B.
Finally, multiply by $$$x!$$$ to account for all the ways you can reach each ending configuration.
Thus, if $$$x=n$$$, there are $$$2 \cdot x!$$$ optimal games, otherwise there are $$$2 \cdot (\binom x {n-x} + \binom {x-1} {n-x-1} ) \cdot x!$$$ optimal games.
Add up the number of games that end in $$$x$$$ moves for all even $$$x$$$ from $$$\lceil \frac{n}{2} \rceil$$$ to $$$n$$$, inclusive. Thus, the solution is $$$O(n)$$$.