← 返回题目列表

Codeforces · 1536/F

F. 奥姆卡和阿克玛

中文机器翻译题面 查看原题

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$$$ 为模进行最佳游戏的可能不同游戏的数量。

示例

输入 #1

2

输出 #1

4

输入 #2

69420

输出 #2

629909355

输入 #3

42069

输出 #3

675837193

注意

对于第一个示例案例,第一个玩家有 $$$4$$$ 可能的移动。无论第一个玩家玩什么,第二个玩家只有 $$$1$$$ 可能的行动,因此有 $$$4$$$ 可能的游戏。