The gnomes have thrown another party. Once again, there were $n$ of them, and each received a pointed hat (from a set of $n$ hats with distinct heights from $1$ to $n$). This time, however, they were all feasting on one side of a long table.

Since the gnomes remembered this party like no other, a local painter decided to immortalize the feast in a painting. To do this, he needs to know who sat where at the table and what hat they wore. The gnomes remember where they sat, but the hats were distributed randomly, and none of the gnomes remembers the height of their own hat. Each of them can only say what hat one of their neighbors at the table had.

Help the painter and write a program that determines the number of possible hat arrangements for the given testimonies of the gnomes. It is sufficient to output the result modulo $10^9 + 7$. If the gnomes were mistaken and the information provided is contradictory, the correct result is $0$.

Input

The first line of the input contains an integer $n$ ($n \ge 2$) representing the number of gnomes.

The second line contains a sequence of $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le n$); the number $h_i$ means that the $i$-th gnome (counting from the left end of the table) told the painter: "one of my neighbors at the table had a hat of height $h_i$".

Output

Your program should output a single line containing an integer representing the number of possible hat arrangements consistent with the gnomes' answers. The result should be given modulo $10^9 + 7$.

Examples

Input 1

5
3 4 3 4 1

Output 1

2

Note

The first gnome definitely describes the hat of the second (so the second has a hat of height $3$), and the fifth gnome describes the hat of the fourth (so the fourth has a hat of height $1$). Furthermore, the second and fourth gnomes remember the hat of height $4$, so it must have been the hat of the third gnome. There are two remaining possibilities for placing the hats $2$ and $5$.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.