1161 : Not the Only Tree

Description

We all know that to build a traditional “Binary Search Tree”, we put the smaller numbers to the left while the larger to the right. Different data insertion order may result in different tree structure.

In this problem, you need to calculate how many different input sequences there are to get a binary search tree with a specific structure.

Input

There are no more than 100 test cases. Each case contains two lines:

The first line is an integer n.

The second line is a permutation of [1, n], describing a Binary Search Tree constructed according to the order of the sequence.

1 ≤ n ≤ 10³.

Output

For each test case, output the number of different sequences which could build a Binary Search Tree with the same structure, including the input one.

The result should be modulo 10⁹ + 7.

Sample

4
3 2 4 1
5
3 5 2 1 4

3
6

Hint

For the first case, 3 2 1 4, 3 2 4 1, 3 4 2 1 could make the same tree:

    3
   / \
  2   4
 /
1

So the answer is 3.

Source

Author

CSGrandeur