Днепропетровск покоряет космос
Всем известно, что Днепропетровск – космическая столица Украины. Ракеты-носители, двигатели и другие устройства для покорения космоса, сделанные на Южном Машиностроительном Заводе известны во всем мире. Совсем недавно, например, была запущена американская ракета-носитель Антарес на двигателях, сделанных в КБ "Южное". В общем, изучение космоса силами Днепропетровска не прекращается.
Очень важной задачей для космических аппаратов является связь с Землёй. Этот процесс решили смоделировать. На компьютер передается перестановка натуральных чисел от 1 до n. При этом возможны погрешности при передаче данных, поэтому вместо некоторого числа a может быть передано число a-1, число a или a+1. Хотелось бы восстановить исходную перестановку по полученному набору данных. Но оказалось, что сделать это однозначно можно не всегда. Ваша задача, как участника традиционного Всеукраинского конкурса "Мирный космос", найти, сколько различных перестановок мог дать такой набор полученных данных.
Входные данные
В первой строке задано число n (1 ≤ n ≤ 10^5). В следующей строке n чисел. Все числа лежат в диапазоне от 0 до n+1.
Выходные данные
Единственное число – ответ на задачу. Так как число может быть очень большим, выведите его остаток при делении на 1000000007 (10^9+7).