题目描述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

提示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.