问题描述

已知一个长度为 $N$ 的数组: $A_{1}, A_{2}, A_{3}, \ldots A_{N}$ 恰好是 $1 \sim 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 \leq N \leq 20$ .

对于 100% 评测用例, $1 \leq N \leq 10000$ .