They did it again! The gnomes held an after-party following their last event*. There were $n$ of them again, and each of them received a pointed hat (from $n$ hats of distinct heights from $1$ to $n$). And again, they all feasted on one side of a long table.

Once again, the local painter will commemorate the party in a painting, so he asks each gnome about the heights of the hats. This time, however, the gnomes remember even less, and each of them can only say what hat their left neighbor had, their right neighbor had, or they themselves 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 provide the remainder when divided by $10^9 + 7$. If the gnomes made a mistake and the information provided by them is mutually contradictory, the correct result is 0.

Input

The first line of the input contains an integer $n$ ($n \ge 2$) denoting 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: "the hat of height $h_i$ was worn by me or one of my neighbors at the table".

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

4
2 4 2 1

Output 1

3

Note

The first and third gnomes remember the hat 2, so it must have been the hat of the second gnome. If the fourth gnome remembers the hat of his neighbor (i.e., the third gnome), then the second gnome must have remembered the hat of the first gnome, so the order of the hats is 4 2 1 3.

If, on the other hand, the fourth gnome remembered the height of his own hat, then we have two possibilities: 4 2 3 1 or 3 2 4 1.

Subtasks

*It took place during the first stage of the competition, in the problem Impreza krasnali.