Problem Description

There are $n$ people standing in a line in sequence, each holding a number, forming a permutation of these $n$ numbers.

Each person will report the number of either the person to their left or the person to their right. Note that the first and the last person are not adjacent, so the first person will always report the number of the second person, and the last person will always report the number of the second-to-last person.

Given the numbers reported by the $n$ people, determine how many possible original permutations exist.

Input Format

The first line contains a positive integer $n$.

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

Output Format

A single line containing an integer, your answer modulo $10^9+7$.

Sample Input and Output

Sample Input #1

5
3 4 3 4 1

Sample Output #1

2

Sample Input #2

(Refer to the attached file)

Sample Output #2

0

Sample Input #3

(Refer to the attached file)

Sample Output #3

1

Notes

For all test cases, $2 \leq n \leq 100000$.

见题面 Input 部分

见题面 Output 部分