You are currently researching a graph traversal algorithm called the Depth First Search (DFS). Starting with an empty list , the following pseudocode will fill the list with the visitation order of a DFS algorithm.
DFS(v):
append v to A
for each u neighbour of v in ascending node number:
if u is not in A:
DFS(u)
After running from the pseudocode above, you now have a list containing a permutation of integers from to . You now wonder how many different simple undirected graphs with nodes there are that yield the list that you have. Count the number, modulo .
A graph is simple when there are no self-loops and there is at most one edge connecting each pair of nodes. Two graphs are considered different if there is an edge connecting a pair of nodes in one graph but not the other.
输入格式
The first line contains an integer ().
The second line contains a permutation of the first positive integers, representing the list .
The first element of is guaranteed to be .
输出格式
A single integer representing the number of different graphs, whose DFS order gives you the list , modulo .
样例
样例输入 1
4
1 3 4 2
样例输出 1
3
样例输入 2
10
1 2 3 4 5 6 7 8 9 10
样例输出 2
515546413
数据范围与提示
The following illustrates all the graphs with the given DFS order.
:::