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$$$ 可能的游戏。