\includegraphics{https://static.e-olymp.com/content/a7/a79de2a50da758b2f420a52b59b5206efcaff18d.jpg} Усім відомо, що Дніпропетровськ -- космічна столиця України. Ракети-носії, двигуни та інші пристрої для підкорення космосу, виготовлені на Південному Машинобудівному Заводі відомі в усьому світі. Зовсім нещодавно, наприклад, була запущена американська ракета-носій Антарес на двигунах, виготовлених у КБ "Південне". Загалом, вивчення космосу силами Дніпропетровська не припиняється. Дуже важливою задачею для космічних апаратів є зв'язок з Землею. Цей процес вирішили промоделювати. На комп'ютер передається перестановка натуральних чисел від \textbf{1} до \textbf{n}. При цьому можливі похибки при передачі даних, тому замість деякого числа \textbf{a} може бути передано число \textbf{a-1}, число \textbf{a} або \textbf{a+1}. Хотілось би відновити початкову перестановку за отриманим набором даних. Але виявилось, що зробити це однозначно можна не завжди. Ваша задача, як участника традиційного Всеукраїнського конкурсу "Мирний космос", знайти, скільки різних перестановок міг дати такий набір отриманих даних. \InputFile У першому рядку задано число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^5}). У наступному рядку \textbf{n} чисел. Усі числа лежать у діапазоні від \textbf{0} до \textbf{n+1}. \OutputFile Єдине число -- відповідь до задачі. Так як число може бути дуже великим, виведіть його остачу при діленні на \textbf{1000000007} (\textbf{10^9+7}).