#P1839. 子序列个数

子序列个数

子序列的定义:对于一个序列a=a[1],a[2],......a[n],则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列,其中1<=p1<p2<.....<pm<=n。 例如:4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。

对于给出序列a,有些子序列可能是相同的,这里只算做1个,要求输出a的不同子序列的数量。

Input

输入包含多组数据(不超过100组)
每组数据有两行:
第一行:整数n(1<=n<=100),代表数组元素个数
第二行:n个整数a[i](0<=a[i]<=110 ),代表数组元素

Output

每组输出单独占一行。
输出子序列的个数对1000000007取余数的结果。

Sample Input

5
1 92 69 52 67
2
1 2

Sample Output

</p>
31
3

HINT

Source