Omkar and Akmar

有一个包含 $n$ 个格子的环形棋盘，棋盘上的格子编号为 $1$ 到 $n$，满足对于任意整数 $i\in[1,n-1]$，格子 $i$ 与格子 $i+1$ 相邻，特别的，格子 $1$ 与格子 $n$ 相邻。 小 A 和小 O 在这个棋盘上轮流操作（小 A 先手）。对于每一轮，每一个人需要选择一个空的格子，并在上面放上字母 `A` 或字母 `B`，要求放完字母后不能存在两个相邻的格子有着相同的字母放在上面。如果轮到一个人时没有合法操作，那么那个人输。 输出当两位玩家每一轮都采用最优操作玩这个游戏时，**游戏结束后**不同的局面数对 $10^9+7$ 取模后的值。 $1\leq n\leq10^6;$ 我们认为两个局面不同，仅当游戏轮数不同，或者对于某一轮，放下的字母或是放下字母的格子不同。 我们认为对于某一轮，一个操作是最优操作仅当这一次操作能够最大化该玩家的获胜机会。换句话讲，如果某位玩家目前有必胜策略，那么他操作之后必须仍然有必胜策略，如果某位玩家没有必胜策略，那么他可以进行任意合法操作。

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.

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

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

2

4

69420

629909355

42069

675837193

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.