题目描述

给定一个只包含整数的序列 (序列元素的绝对值大小不超过 $10^9$)，你需要计算上升子序列的个数，满足如下条件的称之为一个上升子序列：

• 是原序列的一个子序列
• 长度至少为 $2$
• 所有元素都严格递增

如果两个上升子序列相同,那么只需要计算一次。例如：序列 {1, 2, 3, 3} 有 $4$ 个上升子序列，分别为 {1, 2}, {1, 3}, {1, 2, 3}, {2, 3}

输入格式

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

接下来一行是 $n$ 个整数，表示序列。

输出格式

输出仅包含一行,即原序列有多少个上升子序列。

由于答案可能非常大,你只需要输出答案模 $10^9+7$ 的余数。

4
1 2 3 3

4

数据范围

对于 $30\%$ 的数据，$N ≤ 5000$

对于 $100\%$ 的数据，$N ≤ 10^5$