给定一个长度为 $n$ 的数组 $a_1,a_2,\dots ,a_n$,问其中的上升子序列的个数。也就是说,我们要求 数组 $p_1,p_2,\dots,p_m$ 的个数,满足 $1\leq p_1 < p_2 < \dots < p_m \leq n$ 并且 $a_{p_1} < a_{p_2} < \dots < a_{p_m}$。
由于答案很大,输出对$1000000007$取模的结果。
输入格式
第一行一个数字 $n$。
接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$。
输出格式
一个数,表示答案。
样例输入
6
3 7 4 2 6 8
样例输出
23
数据规模
所有数据保证 $1\leq n\leq 1000, 1 \leq a_i \leq 10^9$。