该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个序列 $a_1,a_2,⋯,a_n$，请计算它有多少种不相等子序列数量。由于答案可能很大，输出方案数量模 $10^9+7$ 的余数。

子序列是指从原序列中去除部分数字组成的序列（且留下的数字应保持原序列的顺序），空集不算子序列，原序列本身算是自身的一种子序列。

两个子序列相等，是指他们的长度相同，且对应的每一个数字都相等。比如对于序列 $1,2,1,2,3$ 来说，第一个 $1,2$ 与 第二个 $1,2$ 就是相等的子序列。

输入格式

第一行：单个整数 $n$，代表序列长度 第二行：$n$ 个整数 ，代表 $a_1 到 a_n$

输出格式

单个整数：表示不相等子序列的数量模 $10^9+7$ 的余数。

4 
1 2 3 2

13

样例解释

1、3、13、23、123、2、12、22、122、32、132、232、1232

数据规模与约定

对于 $30$% 的数据，保证 $1≤n≤15$；

对于 $50$% 的数据，保证 $1≤n≤10^3$；

对于 $100$% 的数据，保证 $1≤n≤10^6$；

$1≤a_i≤10^6$。