Зал кинотеатра в городе, в котором живет Сережа, представляет собой n сидений, выстроенных в один ряд перед большим экраном. Слева и справа от каждого сиденья имеется отверстие для личных вещей. При этом у любых двух соседних сидений имеется ровно одно общее отверстие. На рисунке ниже изображено как расположены сиденья и отверстия для n = 4.

Сегодня состоится премьера фильма «Твердый Каштан». Билеты на все места в кинотеатре раскуплены. На входе в зал кинотеатра стоит очень строгий контролер, поэтому все n человек будут заходить в зал по очереди. Как только человек заходит в зал кинотеатра, он сразу (мгновенно) садится на свое место и занимает все свободные отверстия для вещей слева и справа от него. Если же свободных отверстий не оказалось, то человек очень сильно расстараивается и уходит.

Люди очень непостоянны, поэтому сложно предугадать, в каком порядке будут заходить зрители в зал. Для некоторых мест Сережа знает, каким по номеру зайдет в зал зритель, сидящий на этом месте. Для остальных — порядок может быть любой.

Сережу, как программиста и математика, очень волнует вопрос: сколько существует порядков захода людей в зал таких, что никто не будет расстроен. Так как это число может быть достаточно большим, выведите его по модулю 1000000007 (10⁹ + 7).