eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

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

Input data

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

Output data

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

Examples

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