相等子序列

题目描述

给定一个序列 $a_1,a_2,\cdots,a_n$，请计算它有多少种不同的相等子序列。由于答案可能很大，输出方案数量模 $1,000,000,007$ 的余数。

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

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

输入格式

第一行：单个整数 $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 a_i \leq 10^6$

样例输入 #1

4
1 2 3 2

样例输出 #1

13

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐。

测试点分布