Куро только что выиграл соревнование «Самый умный кот». Три друзья решили отпраздновать эту победу, поиграв в различные игры.

Куро попросил Кэти придумать игру, для которой нужны только бумага, карандаш, ножницы и много стрелок (считайте, что стрелок бесконечно много). Кэти тут же придумала игру и назвала ее Топологическая четность.

На бумаге рисуют $$$n$$$ прямоугольников, пронумерованных от $$$1$$$ до $$$n$$$. Широ раскрашивает некоторые прямоугольники в некоторые цвета. А именно, $$$i$$$-й прямоугольник раскрашивается в цвет $$$c_{i}$$$, где $$$c_{i} = 0$$$ означает черный цвет, $$$c_{i} = 1$$$ — белый, а $$$c_{i} = -1$$$ означает, что этот прямоугольник не покрашен.

Правила игры просты. Игроки могут добавлять стрелки между различными прямоугольниками, причем каждая стрелка должна начинаться в прямоугольнике с меньшим номером, чем прямоугольник, в котором она заканчивается. Кроме того, игроки должны выбрать цвет ($$$0$$$ или $$$1$$$) для каждого еще не покрашенного прямоугольника. Между двумя прямоугольниками должно быть не более одной стрелки. Результатом игры будет количество путей из прямоугольников чередующихся цветов. Например, пути, составляющие цвета $$$[1 \to 0 \to 1 \to 0]$$$, $$$[0 \to 1 \to 0 \to 1]$$$, $$$[1]$$$, $$$[0]$$$ будут посчитаны. Из прямоугольника $$$x$$$ можно перейти в прямоугольник $$$y$$$, если и только если есть стрелка из $$$x$$$ в $$$y$$$.

Куро понравилась игра, но он придумал, как сделать ее еще лучше. Он любит играть с четностью чисел. Его любимая четность равна $$$p$$$, где $$$p = 0$$$ обозначает «четное», а $$$p = 1$$$ — «нечетное». Он хочет расставить стрелки и покрасить оставшиеся прямоугольники так, чтобы результат игры имел четность $$$p$$$.

Так как может существовать много вариантов так расставить стрелки и выбрать цвета, посчитайте количество способов сделать это по модулю $$$10^{9} + 7$$$.