P9418 [POI 2021/2022 R1] Impreza krasnali

Translated from [XXIX Olimpiada Informatyczna – Stage I](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Impreza krasnali](https://sio2.mimuw.edu.pl/c/oi29-1/p/imp/).

There are $n$ people standing in a line in order. Each person holds a number, and these $n$ numbers form a permutation. Each person will choose one of two options to report: the number held by the person on their left or the number held by the person on their right. Note that the first person and the $n$-th person are not adjacent, so the first person always reports the second person’s number, and the $n$-th person always reports the $(n-1)$-th person’s number. Now you are given the $n$ numbers reported by the $n$ people. Find how many different original permutations are possible.

The first line contains a positive integer $n$. The second line contains $n$ integers, representing the number reported by each person.

Output one integer: your answer modulo $10^9+7$.

For all testdata, $2\leq n\leq 100000$. | Subtask ID | Additional Constraints | Points | | :----------: | :----------: | :----------: | | 1 | $n\leq 10$ | 12 | | 2 | $n\leq 20$ | 30 | | 3 | $n\leq 1000$ | 30 | | 4 | | 28 | Translated by ChatGPT 5