U516078 最长上升子序列计数

给你一个长度为 $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$ 取模的结果）。

符合要求的子序列有： $$ [3,4,5]\\ [2,4,5] \\ [1,4,5] \\ [2,3,5] \\ [1,3,5] $$