题目描述

给定一个长度为 $n$ 的序列 $A$（$n\le 5000$），求有多少个最长的 $A$ 的子序列，满足除第一个元素外，该子序列的每个元素都大于前一个元素。

• 子序列：序列 $A$ 的子序列是从 $A$ 中将若干元素提取出来并不改变相对位置形成的序列。空序列及原序列本身也是原序列的一个子序列。
• 非空子序列：除了空序列之外的子序列。
• 真子序列：除了原序列本身之外的子序列。
• 非空真子序列：除了空序列及原序列本身之外的子序列。

输入格式

第一行一个数 $n$。

第二行 $n$ 个数 $a_1\sim a_n$。

输出格式

一行一个整数，表示有多少种最长上升子序列。

这个数可能会很大，只需要输出其对 $10^9+7$ 取模后的结果即可。

7
4 2 3 7 6 5 8

3

• $(2,3,7,8),(2,3,6,8),(2,3,5,8)$

6
1 1 2 2 3 3

8

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 5000$，$1\le a_i\le 10^9$。