题目背景

前有连续子序列，接下来，读题很有用。

前无马。

题目描述

给你一个长为 $n$ 的序列 $a_{1\dots n}$，你需要求出其所有本质不同非空子序列的本质不同非空子序列数量之和。

形式化地，你需要求出有多少正整数序列对 $(b_{1\dots l_1},c_{1\dots l_2})$，满足存在两个序列 $p_{1\dots l_1},q_{1\dots l_2}$ 使得：

• $1\le p_1<p_2<\dots<p_{l_1}\le n$；
• $\forall i\in[1,l_1],b_i=a_{p_i}$；
• $1\le q_1<q_2<\dots<q_{l_2}\le l_1$；
• $\forall i\in[1,l_2],c_i=b_{q_i}$。

将答案对 $10^9+7$ 取模。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数描述 $a_{1\dots n}$。

输出格式

一行一个整数表示答案，对 $10^9+7$ 取模。

3
1 2 3

19

3
1 2 2

12

10
5 5 2 5 3 4 1 4 4 3 

15735

提示

样例 1 解释

有如下共 $19$ 种合法序列对：

• $b=(1,2,3),c=(1,2,3)$；
• $b=(1,2,3),c=(1,2)$；
• $b=(1,2,3),c=(1,3)$；
• $b=(1,2,3),c=(2,3)$；
• $b=(1,2,3),c=(1)$；
• $b=(1,2,3),c=(2)$；
• $b=(1,2,3),c=(3)$；
• $b=(1,2),c=(1,2)$；
• $b=(1,2),c=(1)$；
• $b=(1,2),c=(2)$；
• $b=(2,3),c=(2,3)$；
• $b=(2,3),c=(2)$；
• $b=(2,3),c=(3)$；
• $b=(1,3),c=(1,3)$；
• $b=(1,3),c=(1)$；
• $b=(1,3),c=(3)$；
• $b=(1),c=(1)$；
• $b=(2),c=(2)$；
• $b=(3),c=(3)$。

样例 2 解释

有如下共 $12$ 种合法序列对：

• $b=(1,2,2),c=(1,2,2)$；
• $b=(1,2,2),c=(1,2)$；
• $b=(1,2,2),c=(2,2)$；
• $b=(1,2,2),c=(1)$；
• $b=(1,2,2),c=(2)$；
• $b=(1,2),c=(1,2)$；
• $b=(1,2),c=(1)$；
• $b=(1,2),c=(2)$；
• $b=(2,2),c=(2,2)$；
• $b=(2,2),c=(2)$；
• $b=(1),c=(1)$；
• $b=(2),c=(2)$。

数据范围与约定

本题采用捆绑测试。

::cute-table | 子任务编号 | $n\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | 无 | $10$ | | $2$ | $20$ | ^ | $10$ | | $3$ | $100$ | ^ | $15$ | | $4$ | $500$ | ^ | $15$ | | $5$ | $8000$ | $a_i\le 2$ | $15$ | | $6$ | ^ | $a_i\le 5$ | $10$ | | $7$ | ^ | 无 | $25$ |

对于所有数据，保证 $1\le n\le 8000$，$1\le a_i\le n$。

保证本题模数 $\bm{10^9+7}$ 不等于 $\bm{998244853}$ 或 $\bm{2^{23}}$。