蓝桥杯第十三届省赛Java大学B组模拟_问题E

提交: 1398 解决: 368

题目描述

已知一个长度为 N 的数组：A₁, A₂, A₃, ...A_N 恰好是 1 ∼ N 的一个排列。现在要求你将 A 数组切分成若干个 (最少一个，最多 N 个) 连续的子数组，并且每个子数组中包含的整数恰好可以组成一段连续的自然数。

例如对于 A = {1, 3, 2, 4}, 一共有 5 种切分方法：

{1}{3}{2}{4}：每个单独的数显然是 (长度为 1 的) 一段连续的自然数。

{1}{3, 2}{4}：{3, 2} 包含 2 到 3，是 一段连续的自然数，另外 {1} 和 {4} 显然也是。

{1}{3, 2, 4}：{3, 2, 4} 包含 2 到 4，是 一段连续的自然数，另外 {1} 显然也是。

{1, 3, 2}{4}：{1, 3, 2} 包含 1 到 3，是 一段连续的自然数，另外 {4} 显然也是。

{1, 3, 2, 4}：只有一个子数组，包含 1 到 4，是 一段连续的自然数。

输入

第一行包含一个整数 N。第二行包含 N 个整数，代表 A 数组。

输出

输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。

样例输入

4
1 3 2 4

样例输出

提示

对于 30% 评测用例，1 ≤ N ≤ 20.

对于 100% 评测用例，1 ≤ N ≤ 10000.

注意事项：

1. 不要使用 package 语句。

2. 选手代码的主类名必须为：Main，否则会被判为无效代码。

3. 如果程序中引用了类库，在提交时必须将 import 语句与程序的其他部分同时提交。

4. 只允许使用 Java 自带的类库。

5. 提交时，注意选择使用Java语言。