PROGRAMMING:Insertion Sequences of a Binary Search Tree
A binary search tree (BST) can be defined as a binary tree with the following properties:
* The left subtree of a node contains only nodes with keys less than the node's key;
* The right subtree of a node contains only nodes with keys greater than the node's key;
* Both the left and right subtrees are also binary search trees.
There exists different insertion sequences when we try to build a binary search tree. As for the binary search tree shown below,
a valid insertion sequence can be `3 2 1 4 6 5`, or `3 2 4 1 6 5` , but cannot be `3 2 4 5 6 1 `.
Now you are given the pre-order traversal sequence of a binary search tree. Please write a program to calculate the total count of insertion sequences of this tree. Since the total can be very large, you should output the result modulo $$1000000007$$ ($$10^9+7$$) .
#### Input Specification:
Each input file contains one test case. Each test case consists of two lines. In the first line, an integer $$N$$ is given, denoting the count of elements in the binary search tree; and the second line gives the pre-order traversal sequence of the tree, in which numbers are separated by a space.
#### Output Specification:
Output the total count of insertion sequences in a line.
#### Sample Input:
```in
six
3 2 1 4 6 5
```
#### Sample Output:
```out
ten
```
answer：If there is no answer, please comment
* The left subtree of a node contains only nodes with keys less than the node's key;
* The right subtree of a node contains only nodes with keys greater than the node's key;
* Both the left and right subtrees are also binary search trees.
There exists different insertion sequences when we try to build a binary search tree. As for the binary search tree shown below,
a valid insertion sequence can be `3 2 1 4 6 5`, or `3 2 4 1 6 5` , but cannot be `3 2 4 5 6 1 `.
Now you are given the pre-order traversal sequence of a binary search tree. Please write a program to calculate the total count of insertion sequences of this tree. Since the total can be very large, you should output the result modulo $$1000000007$$ ($$10^9+7$$) .
#### Input Specification:
Each input file contains one test case. Each test case consists of two lines. In the first line, an integer $$N$$ is given, denoting the count of elements in the binary search tree; and the second line gives the pre-order traversal sequence of the tree, in which numbers are separated by a space.
#### Output Specification:
Output the total count of insertion sequences in a line.
#### Sample Input:
```in
six
3 2 1 4 6 5
```
#### Sample Output:
```out
ten
```
answer：If there is no answer, please comment