题目描述

已知一个长度为 $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$ 数组。

输出格式

输出一个整数表示答案。由于答案可能很大，所以输出其对 $10^9+7$ 取模后的值。

4
1 3 2 4

5

提示

【评测用例规模与约定】

对于 $30\%$ 评测用例，$1 \leq N \leq 20$.

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