Куро только что выиграл соревнование «Самый умный кот». Три друзья решили отпраздновать эту победу, поиграв в различные игры.
Куро попросил Кэти придумать игру, для которой нужны только бумага, карандаш, ножницы и много стрелок (считайте, что стрелок бесконечно много). Кэти тут же придумала игру и назвала ее Топологическая четность.
На бумаге рисуют \(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\).
Примечание
В первом примере есть \(6\) способов покрасить кусочки и нарисовать стрелки, они показаны на рисунке ниже. Результаты игр в верхней строке равны \(3, 3, 5\), во второй — \(5, 3, 3\), слева направо.
