P9418 [POI 2021/2022 R1] Impreza krasnali

译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Impreza krasnali](https://sio2.mimuw.edu.pl/c/oi29-1/p/imp/)。

有 $n$ 个人依次站成一排，每个人手上都有一个数字，这 $n$ 个数字形成一个排列。 每个人会二选一地报告他左边或右边的人手上的数字。注意第一个人与第 $n$ 个人并不相邻，所以第一个人总是会报告第二个人的数字，第 $n$ 个人总是会报告第 $n-1$ 个人的数字。 现在你得到了 $n$ 个人报告的数字，求出原先的排列有多少种可能。

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

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

对于所有数据，$2\leq n\leq 100000$。 | 子任务编号 | 附加限制 | 分数 | | :----------: | :----------: | :----------: | | 1 | $n\leq 10$ | 12 | | 2 | $n\leq 20$ | 30 | | 3 | $n\leq 1000$ | 30 | | 4 | | 28 |