← 返回题目列表

Codeforces · 509/F

F. 进度监控

中文机器翻译题面 查看原题

编程老师 Dmitry Olegovich 将为他的学生测试之一提出以下任务:

给定一棵有 n 个顶点的树 T,由其邻接矩阵 a[1...n, 1...n] 指定。下面的伪代码的输出是什么?

为了简化测试结果检查程序,Dmitry Olegovich 决定创建一棵树 T,使得结果是他最喜欢的序列 b。另一方面,Dmitry Olegovich 不想为学生提供相同的树作为输入,否则他们可能会作弊。这就是为什么 Dmitry Olegovich 试图找出不同树 T 的数量,使得以 T 作为输入运行上述伪代码的结果正是序列 b。你能帮助他吗?

如果两棵有 n 个顶点的树的邻接矩阵 a1 和 a2 不同,则称它们不同。 e.存在一对 (i, j),使得 1 ≤ i,j ≤ n 且 a1[i][j] ≠ a2[i][j]。

输入

第一行包含正整数 n (1 ≤ n ≤ 500) — 序列 b 的长度。

第二行包含 n 个正整数 b1, b2, ..., bn (1 ≤ bi ≤ n)。保证b是一个排列,或者换句话说,每个数字1,2,...,n在序列b中只出现一次。还保证 b1 = 1。

输出

输出满足上述条件模 109 + 7 的树的数量。

示例

输入 #1

3
1 2 3

输出 #1

2

输入 #2

3
1 3 2

输出 #2

1