G. Domain Expansion
time limit per test
2.5 с
memory limit per test
128 МБ
input
standard input
output
standard output

Tyger has an array $$$a$$$ that is initially $$$[0]$$$.

He can do any number of Domain Expansions to the array. Each Domain Expansion allows him to first choose any index $$$i$$$, then insert $$$a_i+1$$$ on either the left or right side of the element $$$a_i$$$. Tyger wants to create a target array $$$b$$$ of length $$$n$$$, please help him count the number of ways to get target array $$$b$$$, modulo $$$10^9+7$$$.

Two ways are different if a Domain Expansion (which accounts for both position chosen and whether the new element is inserted left or right) is different at any position.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 400)$$$, the length of the target array $$$b$$$.

The next line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ $$$(0 \leq b_i \leq 10^9)$$$, representing the target array.

Output

Output a single integer, the number of different ways to get target array $$$b$$$ modulo $$$10^9 + 7$$$.

Scoring

In tests worth $$$10$$$ points, it is guaranteed that $$$b_i = i - 1$$$ for all $$$1 \leq i \leq n$$$.

In tests worth $$$10$$$ points, it is guaranteed that $$$1 \leq n \leq 80$$$.

Example
Input
4
1 2 1 0
Output
3
Note

One of the ways to get target array $$$b$$$ is through this sequence of Domain Expansions: 

[0] -> [1, 0] -> [1, 2, 0] -> [1, 2, 1, 0]

Another way is 

[0] -> [1, 0] -> [1, 1, 0] -> [1, 2, 1, 0]

Note that this sequence actually accounts for two different ways because the $$$2$$$ can be inserted both by choosing the first $$$1$$$ (and picking right) and choosing the second $$$1$$$ (and picking left).

Credit: Jasonwei08