Омкар и Акмар играют в игру на круговой доске с $$$n$$$ ($$$2 \leq n \leq 10^6$$$) клетками. Клетки пронумерованы от $$$1$$$ до $$$n$$$, для каждой $$$i$$$ ($$$1 \leq i \leq n-1$$$) клетка $$$i$$$ соседствует с клеткой $$$i+1$$$, а клетка $$$1$$$ соседствует с клеткой $$$n$$$. Изначально каждая клетка пуста.

Омкар и Акмар по очереди выкладывают на доску букву A или B, причем Акмар ходит первым. Буква должна быть помещена на пустую клетку. Кроме того, буква не может быть помещена в такую клетку, что соседняя клетка содержит ту же букву.

Игрок проигрывает, когда наступает его очередь и больше нет допустимых ходов.

Выведите количество возможных различных игр, в которых оба игрока играют оптимально по модулю $$$10^9+7$$$. Обратите внимание, что мы рассматриваем только те партии, в которых кто-то из игроков проиграл, и не осталось ни одного допустимого хода.

Две игры считаются разными, если количества ходов в них отличаются, или на каком-то ходу буква или номер клетки, на которую ставится буква, были разными.

Ход считается оптимальным, если он максимизирует шансы игрока на победу, предполагая, что другой игрок также играет оптимально. Более формально, если игрок, чья очередь ходить, имеет выигрышную стратегию, он должен сделать ход, после которого у него останется выигрышная стратегия. Если же у него ее нет, то он может сделать любой ход.