问题描述

已知一个长度为 $N$ 的数组：$A_1, A_2, A_3, \dots, A_N$，它恰好是 $1 \sim N$ 的一个排列。

现在要求你将数组 $A$ 切分成若干个（最少一个，最多 $N$ 个）连续的子数组，并且每个子数组中包含的整数恰好可以组成一段连续的自然数。

例如，对于 $A = [1, 3, 2, 4]$，一共有 $5$ 种切分方法：

• $\lbrace 1 \rbrace, \lbrace 3 \rbrace, \lbrace 2 \rbrace, \lbrace 4 \rbrace$ ：每个单独的数显然是长度为 $1$ 的连续自然数段。
• $\lbrace 1 \rbrace, \lbrace 3, 2 \rbrace, \lbrace 4 \rbrace$ ：${3, 2}$ 包含 $2 \sim 3$，是一段连续的自然数，另外 $1$ 和 $4$ 显然也是。
• $\lbrace 1 \rbrace, \lbrace 3, 2, 4 \rbrace$ ：${3, 2, 4}$ 包含 $2 \sim 4$，是一段连续的自然数，另外 $1$ 也显然成立。
• $\lbrace 1, 3, 2 \rbrace, \lbrace 4 \rbrace$ ：${1, 3, 2}$ 包含 $1 \sim 3$，是一段连续的自然数，另外 $4$ 也成立。
• $\lbrace 1, 3, 2, 4 \rbrace$ ：只有一个子数组，包含 $1 \sim 4$，是一段连续的自然数。

输入格式

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

输出格式

输出一个整数，表示切分方法数目对 $1000000007$ 取模后的结果。

样例输入

4
1 3 2 4

样例输出

5

数据范围

对于 $30\%$ 的数据，$1 \le N \le 20$；

对于 $100\%$ 的数据，$1 \le N \le 10000$。