题目背景

译自 XXIX Olimpiada Informatyczna – I etap Impreza krasnali。

题目描述

有 $n$ 个人依次站成一排，每个人手上都有一个数字，这 $n$ 个数字形成一个排列。

每个人会二选一地报告他左边或右边的人手上的数字。注意第一个人与第 $n$ 个人并不相邻，所以第一个人总是会报告第二个人的数字，第 $n$ 个人总是会报告第 $n-1$ 个人的数字。

现在你得到了 $n$ 个人报告的数字，求出原先的排列有多少种可能。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个整数，表示每个人报告的数字。

输出格式

一行一个整数，你的答案模 $10^9+7$。

5
3 4 3 4 1

2

见附件

0

见附件

1

提示

对于所有数据，$2\leq n\leq 100000$。