D. Сережа и кинотеатр
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

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

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

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

Входные данные

Первая строка содержит целое число n (1 ≤ n ≤ 105). Вторая строка содержит n целых чисел, i-ое число — либо каким по номеру будет человек, у которого билет на i-ое место, либо 0, если его порядковый номер не известен. Гарантируется, что все положительные числа во второй строке будут различны.

Считайте, что порядковый номер зашедшего в зал — это уникальное целое число от 1 до n. Человек, имеющий порядковый номер 1, зайдет первым в зал, человек, имеющий порядковый номер 2, зайдет вторым в зал и так далее.

Выходные данные

В единственную строку выведите остаток от деления ответа на число 1000000007 (109 + 7).

Примеры
Входные данные
11
0 0 0 0 0 0 0 0 0 0 0
Выходные данные
1024
Входные данные
6
0 3 1 0 0 0
Выходные данные
3