Background

Translated from XXIX Olimpiada Informatyczna – Stage I Impreza krasnali.

Problem Description

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.

Input Format

The first line contains a positive integer $n$.

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

Output Format

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

5
3 4 3 4 1

2

见附件

0

见附件

1

Hint

For all testdata, $2\leq n\leq 100000$.

Translated by ChatGPT 5