题目描述
给定一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$，请计算它有多少个本质不同的子序列。由于答案可能很大，输出方案数量模 $1,000,000,007$ 的余数。
子序列是从原序列去除部分数字组成的新序列，不能为空，原序列本身也算是自身的子序列。两个子序列长度不同，则算是不相同的，若长度相同，且对应的数字完全一致，就算这些数字在原序列中的位置不完全相同，也被视作是本质相同的。
输入
第一行：单个整数 $n$，代表序列长度
第二行：$n$ 个整数 ，代表 $a_1$ 到 $a_n$
输出
单个整数：表示本质不同的子序列个数模 $10^9+7$的余数。
样例输入输出
提示
+ 对于 $30\%$ 的数据，保证 $1\leq n\leq 15$；
+ 对于 $50\%$ 的数据，保证 $1\leq n\leq 10^3$；
+ 对于 $100\%$ 的数据，保证 $1\leq n\leq 10^6$；
+ $1\leq ai\leq 10^6$