CF1536F.Omkar and Akmar

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.

Omkar 和 Akmar 在一个包含 $n$（$2 \leq n \leq 10^6$）个格子的环形棋盘上进行游戏。格子编号为 $1$ 到 $n$，使得对每个 $i$（$1 \leq i \leq n-1$），格子 $i$ 与格子 $i+1$ 相邻，且格子 $1$ 与格子 $n$ 相邻。初始时，每个格子均为空。

Omkar 和 Akmar 轮流在棋盘上放置字母 A 或 B，Akmar 先手。每次必须将字母放在一个空格子中，且该字母不能被放置在与相同字母相邻的格子上（即：若某格已放置字母 A，则其相邻格子不能再放 A；B 同理）。

当轮到某玩家行动时，若已无合法移动，则该玩家判负。

请输出在双方均以最优策略进行游戏的前提下，所有可能的不同游戏局面总数对 $10^9+7$ 取模的结果。注意：我们只考虑某一方已判负、且再无合法移动的游戏（即游戏已结束）。

若两个游戏的回合数不同，或在某一回合中所放置的字母不同，或所放置的格子编号不同，则认为这两个游戏是不同的。

所谓“最优移动”，是指该移动能最大化当前玩家的获胜概率（假设对手也始终采取最优策略）。更严格地说：若当前需行动的玩家存在必胜策略，则他必须选择一个移动，使得移动后自己仍保持必胜策略；若当前玩家不存在必胜策略，则他可任意选择一个合法移动。

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

唯一的一行包含一个整数 $n$（$2 \leq n \leq 10^6$）—— 表示棋盘上的格子数量。

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

输出一个整数——双方均以最优策略进行游戏时，可能的不同游戏数量对 $10^9+7$ 取模的结果。

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.

对于第一个样例，先手玩家有 $4$ 种可能的走法。无论先手玩家如何走，后手玩家都只有 $1$ 种可能的走法，因此共有 $4$ 种可能的游戏。