CF1536F Omkar and Akmar

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 先手。每次只能在空格子上放置字母，并且不能将字母放在与相同字母相邻的格子上。 当轮到某个玩家时，如果没有合法的落子位置，则该玩家输掉游戏。 请输出在双方都采取最优策略的情况下，可能出现的不同游戏的数量，对 $10^9+7$ 取模。注意，只考虑某位玩家已经输掉且没有更多合法落子的完整游戏。 如果两局游戏的步数不同，或者某一步所放的字母或位置不同，则认为这两局游戏是不同的。 如果某位玩家有必胜策略，则他必须选择能保证自己继续获胜的走法；如果没有，则可以任意走。

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

输出一个整数，表示在双方都采取最优策略的情况下，可能出现的不同游戏的数量，对 $10^9+7$ 取模。

对于第一个样例，先手有 $4$ 种可能的走法。无论先手如何选择，后手只有 $1$ 种可能的走法，所以总共有 $4$ 种不同的游戏。 由 ChatGPT 4.1 翻译