T663805 最长递增子序列的个数

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。 子序列定义为在不改变相对顺序的前提下，选取若干个元素形成的新序列。若子序列严格递增，则称其为**递增子序列**。 请你计算**最长递增子序列（LIS）**的**个数**。 若存在多个不同的最长递增子序列，请将它们全部计数；仅长度最长的计入答案。 答案对 10000007 取模。

第一行一个整数 $n$。 第二行包含 $n$ 个整数 $a_i$。

输出一个整数，表示数组中**最长递增子序列的个数**。

* $1 \le n \le 2000$ * $-10^6 \le a_i \le 10^6$