古卷收藏中的平衡摆放

题目描述

在一座古老的书阁中，馆长需要把一批珍贵古卷依次摆放在一排展台上。第 $i$ 卷古卷的珍稀度被评估为一个整数 $v_i$。

为了方便参观者理解古卷的发展脉络，馆长希望从中选出若干卷古卷，按照原有的顺序摆在一条展线上，使得这条展线上古卷的珍稀度看起来“越往后越珍贵”，也就是后面一卷的珍稀度要不低于前面一卷的珍稀度。

但是馆长还收到了一份统计任务：他想知道，有多少种不同的“最珍贵展线”摆放方案。更加具体地：

• 如果可以选出若干位置 $i_1<i_2<\dots<i_k$，使得$$v_{i_1} \le v_{i_2} \le \dots \le v_{i_k},$$ 并且 $k$ 在所有满足条件的选择方式中是最大的，那么称这是一种“最优展线方案”；
• 两种方案只要在选取的下标序列上不同，就视为不同方案。

请你计算：最优展线方案一共有多少种。

输入格式

输入共两行。

• 第一行包含一个整数 $n$，表示古卷的数量。
• 第二行包含 $n$ 个整数 $v_1,v_2,\dots,v_n$，依次表示每卷古卷的珍稀度，整数之间用一个空格分隔。

输出格式

输出一行，一个整数，表示最优展线方案的数量。

如果最优展线方案数量非常大，你只需要输出真实答案对 $10^9+7$ 取模后的结果。

输入输出样例 #1

输入 #1

4
1 2 2 3

输出 #1

3

样例解释 #1

在这组数据中，最长的“珍稀度不下降”展线长度为 $4$。一共有 $3$ 种不同的最优方案：

• 选择下标序列 $(1,2,3,4)$，珍稀度为 $1,2,2,3$；
• 选择下标序列 $(1,2,4)$，珍稀度为 $1,2,3$；
• 选择下标序列 $(1,3,4)$，珍稀度为 $1,2,3$。

因此答案为 $3$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 2000$；
• 对于所有 $1 \le i \le n$，有 $1 \le v_i \le 10^9$。