CF509F.Progress Monitoring

Programming teacher Dmitry Olegovich is going to propose the following task for one of his tests for students:

You are given a tree T with n vertices, specified by its adjacency matrix a[1... n, 1... n]. What is the output of the following pseudocode?

used[1 ... n] = {0, ..., 0};

procedure dfs(v):
print v;
used[v] = 1;
for i = 1, 2, ..., n:
if (a[v][i] == 1 and used[i] == 0):
dfs(i);

dfs(1);

In order to simplify the test results checking procedure, Dmitry Olegovich decided to create a tree T such that the result is his favorite sequence b. On the other hand, Dmitry Olegovich doesn't want to provide students with same trees as input, otherwise they might cheat. That's why Dmitry Olegovich is trying to find out the number of different trees T such that the result of running the above pseudocode with T as input is exactly the sequence b. Can you help him?

Two trees with n vertices are called different if their adjacency matrices _a_1 and _a_2 are different, i. e. there exists a pair (i, j), such that 1 ≤ i, j ≤ n and _a_1[i][j] ≠ _a_2[i][j].

编程教师德米特里·奥列戈维奇打算在一次面向学生的测试中提出如下题目：

给定一棵包含 $n$ 个顶点的树 $T$，其邻接矩阵为 $a[1\ldots n,\,1\ldots n]$。执行以下伪代码后输出的结果是什么？

used[1 ... n] = {0, ..., 0};  

procedure dfs(v):
    print v;
    used[v] = 1;
    for i = 1, 2, ..., n:
        if (a[v][i] == 1 and used[i] == 0):
            dfs(i);

dfs(1);

为了简化测试结果的判分流程，德米特里·奥列戈维奇决定构造一棵树 $T$，使得上述伪代码的输出恰好是他最喜爱的序列 $b$。另一方面，德米特里·奥列戈维奇不希望向学生提供完全相同的树作为输入，否则学生可能作弊。因此，他试图找出满足如下条件的不同树 $T$ 的数量：以 $T$ 作为输入运行上述伪代码所得到的输出序列恰好为序列 $b$。你能帮他解决这个问题吗？

对于 $n$ 个顶点的两棵树，若它们的邻接矩阵 $a_1$ 和 $a_2$ 不同，则称这两棵树不同；即存在一对下标 $(i,\,j)$，满足 $1 \le i,\,j \le n$ 且 $a_1[i][j] \ne a_2[i][j]$。

The first line contains the positive integer n (1 ≤ n ≤ 500) — the length of sequence b.

The second line contains n positive integers _b_1, _b_2, ..., b__n (1 ≤ b__i ≤ n). It is guaranteed that b is a permutation, or in other words, each of the numbers 1, 2, ..., n appears exactly once in the sequence b. Also it is guaranteed that _b_1 = 1.

第一行包含一个正整数 $n$（$1 \leq n \leq 500$）——序列 $b$ 的长度。

第二行包含 $n$ 个正整数 $b_1,\ b_2,\ \dots,\ b_n$（$1 \leq b_i \leq n$）。保证 $b$ 是一个排列，即数字 $1,\ 2,\ \dots,\ n$ 在序列 $b$ 中恰好各出现一次。此外，还保证 $b_1 = 1$。

Output the number of trees satisfying the conditions above modulo 109 + 7.

输出满足上述条件的树的数量，对 $10^9 + 7$ 取模。