题目描述
给定一个数列 $a_1,a_2,\cdots,a_n$，可以求出它的最长严格上升子序列的长度。请统计，该数列有多少个本质不同的最长严格上升子序列。
所谓本质不同，是指子序列中至少有一个数字的值与其他子序列是不同的。例如对于 $1,2,3,1,2,3$，最长严格上升子序列是 $1,2,3$，这个最长子序列是唯一的，尽管有多个 $1$ 可以成为这个子序列的元素。由于答案可能很大，输出答案模 $10^9+7$ 的余数。
输入
第一行：单个正整数 $n$；
第二行：$n$ 个正整数 $a_1,a_2,\cdots,a_n$。
输出
单个正整数：表示本质不同的最长上升子序列的数量模 $10^9+7$ 的余数。
样例输入输出
提示
+ 对于 $30\%$ 的数据，$1\leq n\leq 100$；
+ 对于 $60\%$ 的数据，$1\leq n\leq 2000$；
+ 对于 $100\%$ 的数据，$1\leq n\leq 100,000$，
+ $1\leq a_i\leq n$。
样例2说明:第一项可以选1或2，第二项可以选3或4，第三项可以选5或6