数组A包括N个整数（可能包括同样的值）。

设S为A的子序列且S中的元素是递增的，则S为A的递增子序列。假设S的长度是全部递增子序列中最长的，则称S为A的最长递增子序列（LIS）。

A的LIS可能有非常多个。比如A为：{1 3 2 0 4}，1 3 4，1 2 4均为A的LIS。

给出数组A，求A的LIS有多少个。

因为数量非常大，输出Mod 1000000007的结果就可以。

同样的数字在不同的位置，算作不同的。比如 {1 1 2} 答案为2。

第1行：1个数N，表示数组的长度。(1 <= N <= 50000)
第2 - N + 1行：每行1个数A[i]，表示数组的元素(0 <= A[i] <= 10^9)

输出最长递增子序列的数量Mod 1000000007。