本题是 http://oj.daimayuan.top/problem/326 的加强版，差别仅在于 $n$ 与 $a_i$ 的取值。

求最长上升子序列及其长度的问题已经相当普及，本题希望你求解 最长上升子序列的个数。

只要有序元组有一个值不同，就称不同。如 $[1, \color{green}{3}$ $,\color{red}{3}$ $, 0, 4]$ 中 $[1, \color{green}{3}$ $, 4], [1,\color{red}{3}$ $, 4]$ 算作两个答案。

输入格式

输入包含两行，第一行有一个整数 $n$，表示序列 $\{a\}$ 的大小。

接下来一行包含 $n$ 个用空格分隔的整数，依次表示 $a_1, a_2, \cdots, a_n$。

输出格式

输出最长上升子序列的个数。

由于这个值可能很大，你只需要输出其模余 $10^9 + 7$ 的结果。

数据规模

• $1 \le n \le 4 \times 10 ^ 5$
• $a_i \in [-10 ^ 8, 10 ^ 8]$

样例 1 输入

5
1 3 3 0 4

样例 1 输出

2

样例 2 输入

8
1 2 4 2 4 7 3 4

样例 2 输出

5

解释：

共包含：

$[1, 2, 4, 7] \times 3$

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