eolymp
Competitions

III Open Distance Programming Olympiad name V.L.Didkovsky 2013-2014

Днепропетровск покоряет космос

prb4548 Всем известно, что Днепропетровск – космическая столица Украины. Ракеты-носители, двигатели и другие устройства для покорения космоса, сделанные на Южном Машиностроительном Заводе известны во всем мире. Совсем недавно, например, была запущена американская ракета-носитель Антарес на двигателях, сделанных в КБ "Южное". В общем, изучение космоса силами Днепропетровска не прекращается.

Очень важной задачей для космических аппаратов является связь с Землёй. Этот процесс решили смоделировать. На компьютер передается перестановка натуральных чисел от 1 до n. При этом возможны погрешности при передаче данных, поэтому вместо некоторого числа a может быть передано число a-1, число a или a+1. Хотелось бы восстановить исходную перестановку по полученному набору данных. Но оказалось, что сделать это однозначно можно не всегда. Ваша задача, как участника традиционного Всеукраинского конкурса "Мирный космос", найти, сколько различных перестановок мог дать такой набор полученных данных.

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

В первой строке задано число n (1n105). В следующей строке n чисел. Все числа лежат в диапазоне от 0 до n+1.

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

Единственное число – ответ на задачу. Так как число может быть очень большим, выведите его остаток при делении на 1000000007 (109+7).

Time limit 1 second
Memory limit 64 MiB
Input example #1
3
1 2 3
Output example #1
3
Author Андрей Селиванов
Source III Открытая Дистанционная Олимпиада 2013-2014 им. В.Л.Дидковского