Problem E
Dwarves Party

The dwarves had a party. There were $n$ of them, and each of them got a pointy hat (out of $n$ hats of different heights from $1$ to $n$). They all feasted on one side of a long table. A local painter will memorialize the party in a painting, so he’ll ask each of the dwarves about their hat heights. Unfortunately, the dwarves remember very little and each of them can only tell what hat their left neighbor had, or his right neighbor, or himself.

Help the painter and write a program that determines the number of possible hat orderings for given dwarves’ testimonies. All you need is the remainder of dividing the answer by $10^9+7$. If the dwarves are mistaken and the information they give contradicts each other, the correct result is 0.

Input

In the first line of the input there is an integer $n$ ($n \geq 2$) specifying the number of dwarves.

In the second line is a sequence of $n$ integers $h_1, h_2, \ldots , h_ n$ ($1 \leq h_ i \leq n$); the number $h_ i$ indicates that the $i$-th dwarf (counting from the left end of the table) said to the painter: “a hat of height $h_ i$ belonged to me or one of my neighbors at the table”.

Output

Your program should output a single line containing an integer denoting the number of possible combinations of hats according to the answers of the dwarves. The result is to be given modulo $10^9+7$.

Explanation of Sample

The first and third dwarves remember hat 2, so surely it was the hat of the second dwarf. If the fourth dwarf remembers the hat of his neighbor (that is, the third dwarf), then the second dwarf must have remembered the hat of the first dwarf, so the order of hats is 4 2 1 3.

If, on the other hand, the fourth dwarf has memorized the height of his hat, then we have two possibilities: 4 2 3 1 or 3 2 4 1.

Scoring

The tests are divided into the following subtasks. The tests for each subtask consist of one or more separate test groups.

4
2 4 2 1

3