题目描述

编程老师 Dmitry Olegovich（以下简称小 D）准备在一次考试中出以下题目： 以邻接矩阵的方式给定一棵树，求下面这段伪代码的输出结果。

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);

为了简化测试结果的检查过程 （其实就是懒） ，小 D 决定创建一棵树 $T$，使得结果是他最喜欢的序列 $b$。不过，小 D 不想为学生用相同的树作为输入（这意味着他们可能会作弊）。所以小 D 试图找出不同的树 $T$ 的数量，以便以 $T$ 作为输入运行上述伪代码的结果恰好是序列 $b$，答案对 $10 ^9+7$ 取模。

（两棵树不同的定义：它们的邻接矩阵不相同）

输入格式

第一行一个整数 $n$，代表题目中序列 $b$ 的长度，$1\le n \le 500$。

第二行 $n$ 个整数，表示序列 $b$（题目确保这是一个$1 \sim n$的排列，而且 $b_1=1$）。

输出格式

一行一个整数表示答案，意思如题面所述。

3
1 2 3

2

3
1 3 2

1