题目描述

正在建设中的建筑物按顺序排列在一行上，编号从左到右为$1, 2, \ldots, N$。

给定长度为$N$的整数序列$X$。建筑物$i$的高度$H_i$可以是介于$1$和$X_i$（包括$X_i$）之间的整数。

对于每个$1 \leq i \leq N$，我们定义$P_i$如下：

• 如果存在一个整数$j (1 \leq j < i)$，使得$H_j > H_i$，那么$P_i$是所有满足条件的$j$中的最大值。否则，$P_i$等于$-1$。

在考虑建筑物高度的所有可能组合情况下，求满足条件的$P$的整数序列的数量，对$1000000007$取模。

约束条件

• $1 \leq N \leq 100$
• $1 \leq X_i \leq 10^5$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $X_1$ $X_2$ $\cdots$ $X_N$

输出

在考虑建筑物高度的所有可能组合情况下，输出满足条件的$P$的整数序列的数量，对$1000000007$取模。

示例输入1

3
3 2 1

示例输出1

4

我们有六种可能的$H$，如下所示：

• $H = (1, 1, 1)$，此时$P$是$(-1, -1, -1)$；
• $H = (1, 2, 1)$，此时$P$是$(-1, -1, 2)$；
• $H = (2, 1, 1)$，此时$P$是$(-1, 1, 1)$；
• $H = (2, 2, 1)$，此时$P$是$(-1, -1, 2)$；
• $H = (3, 1, 1)$，此时$P$是$(-1, 1, 1)$；
• $H = (3, 2, 1)$，此时$P$是$(-1, 1, 2)$。

因此，满足条件的$P$的整数序列的数量为$4$，分别是$(-1, -1, -1), (-1, -1, 2), (-1, 1, 1)$和$(-1, 1, 2)$。

示例输入2

3
1 1 2

示例输出2

1

我们有两个可能的$H$，如下所示：

• $H = (1, 1, 1)$，此时$P$是$(-1, -1, -1)$；
• $H = (1, 1, 2)$，此时$P$是$(-1, -1, -1)$。

因此，满足条件的$P$的整数序列的数量为$1$。

示例输入3

5
2 2 2 2 2

示例输出3

16

示例输入4

13
3 1 4 1 5 9 2 6 5 3 5 8 9

示例输出4

31155