P3970 [TJOI2014] 上升子序列

给定一个只包含整数的序列（序列元素的绝对值大小不超过 $10^9$），你需要计算上升子序列的个数，满足如下条件的称之为一个上升子序列： 1. 是原序列的一个子序列 2. 长度至少为 $2$ 3. 所有元素都严格递增 如果两个上升子序列相同，那么只需要计算一次。例如，序列 $\{1,2,3,3\}$ 有 $4$ 个上升子序列，分别为 $\{1,2\}$，$\{1,3\}$，$\{1,2,3\}$，$\{2,3\}$。

输入的第一行是一个整数 $n$，表示序列长度。接下来一行是 $n$ 个整数，表示序列。

输出仅包含一行，即原序列有多少个上升子序列。由于答案可能非常大，你只需要输出答案模 $10^9+7$ 的余数。

### 数据范围 对于 $30\%$ 的数据，$n\le5000$； 对于 $100\%$ 的数据，$n\le10^5$。