题目描述

给你一个长度为 $n$ 的序列 $a_1\sim a_n$，请你求出该序列中有多少个不同的最长上升子序列（两个子序列 $x$ 和 $y$ 不同当且仅当 $x$ 和 $y$ 在原序列中的下标集合不同 ）。
定义一组序列 $b_1\sim b_m$ 是 $a_1\sim a_n$ 的子序列当且仅当 $b$ 可以通过 $a$ 删除若干个元素（也可以不删）后剩下的元素保持相对顺序不变形成。
例如：序列 $a=[1,2,3,4,5]$，序列 $b=[2,4,5]$ 是 $a$ 的子序列。

输入格式

第一行一个整数 $n(1\le n\le 5000)$。
第二行 $n$ 个整数 $a_1\sim a_n(1\le a_i\le 10^9)$。

输出格式

一行一个整数，表示最长上升子序列的个数（输出答案对 $10^9+7$ 取模的结果）。

输入输出样例 #1

输入 #1

6
3 2 1 4 3 5

输出 #1

5

说明/提示

符合要求的子序列有：

$$[3,4,5]\\ [2,4,5] \\ [1,4,5] \\ [2,3,5] \\ [1,3,5] $$