不

题号：NC292115
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ ⭐我喜欢梧桐树下藏匿着四季的梦

$\hspace{15pt}$ 给定一个长度为 $n$ 的序列 $\{a_1, a_2, \dots, a_n\}$ ，求有多少个非空子序列 $\Bbb{S}$ 满足以下条件： $\text{Mex}(\Bbb{S}) \geq \text{Max}(\Bbb{S}) - \text{Min}(\Bbb{S})$

$\hspace{15pt}$ 其中：
$\hspace{23pt}\bullet\,$ $\Bbb{S}$ 是一个子序列 $a_{x_1}, a_{x_2}, \dots, a_{x_k}$ （ $1 \leqq x_1 <$ $x_2 < \dots < x_k \leqq n$ ）。
$\hspace{23pt}\bullet\,$ $\text{Mex}(\Bbb{S})$ 表示 $\Bbb{S}$ 中未出现的最小非负整数。
$\hspace{23pt}\bullet\,$ $\text{Max}(\Bbb{S})$ 和 $\text{Min}(\Bbb{S})$ 分别表示 $\Bbb{S}$ 中的最大值和最小值。
$\hspace{15pt}$ 由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

$\hspace{15pt}$ 子序列为从原数组中删除任意个（可以为零、可以为全部）元素得到的新数组。

输入描述:

第一行输入一个整数 。 
第二行输入  个整数 。

输出描述:

一个整数，表示满足条件的非空子序列的数量。由于答案可能很大，请将答案对  取模后输出。

示例1

输入

复制

3
0 1 2

输出

复制

说明

在这个样例中，所有非空子序列为：
, , , , 满足 ；
, , , , 满足 ；
, , , , 满足 ；
, , , , 满足 ；
, , , , 满足 （不满足，不计入）；
, , , , 满足 （不满足，不计入）；
, , , , 满足 ；
共有  个子序列满足条件。