题目背景

倘若天下无神，这里便是人的国度。

题目描述

你将主持一场祭祀，祭祀会使用到 $N$ 块排成一列的玉石，玉石从左至右依次编号为 $1,2,\cdots,N$。玉石 $i$ 的颜色为 $a_i$。

每一轮祭祀，你需要选择一段颜色相同的玉石 $a_l \sim a_r(1\le l \le r\le N\le 50)$，并将它们沉入水中。本次祭祀的仙力值 $K$ 将变为 $10000\cdot K+100\cdot l+r$，$K$ 的初始值为 $0$。

一段玉石被沉入水中后，右侧的玉石会向左移动。同时，编号也会发生变化，从左至右依次编号为 $1,2,\cdots$。例如，共有 $7$ 块玉石，颜色依次为 $1,1,2,2,2,3,2$。一开始，颜色为 $3$ 的玉石编号为 $6$，在 $3\sim 5$ 号玉石被沉入水中后，其编号将变为 $3$。

当所有玉石被沉入水中，祭祀完成，此时的仙力值即为本次祭祀的仙力值。请问祭祀完成后，一共可能得到多少种不同的仙力值？

由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的值。

输入格式

输入共两行。

输入的第一行为一个正整数 $N$，表示玉石的个数。

输入的第二行为 $N$ 个正整数 $a_1,a_2,\cdots,a_N$，其中 $a_i$ 表示第 $i$ 块玉石的颜色。

输出格式

输出一行一个整数，表示不同仙力值的种数对 $10^9+7$ 取模的结果。

1
1

1

3
3 3 1

8

5
1 2 1 2 1

165

见选手目录下的 jade/jade4.in 与 jade/jade4.ans。

该样例满足测试点 5 ∼ 8 的限制。

见选手目录下的 jade/jade5.in 与 jade/jade5.ans。

该样例满足测试点 9 ∼ 12 的限制。

见选手目录下的 jade/jade6.in 与 jade/jade6.ans。

该样例满足测试点 13 ∼ 16 的限制。

见选手目录下的 jade/jade7.in 与 jade/jade7.ans。

提示

样例解释 3

这里列举两种可能得到的仙力值和得到的方式：

1. $(1,\underline{2},1,2,1) \xrightarrow{K=202} (1,1,\underline{2},1) \xrightarrow{K=2\ 020\ 303} (\underline{1},\underline{1},1) \xrightarrow{K=20\ 203\ 030\ 102} (\underline{1}) \xrightarrow{K=202\ 030\ 301\ 020\ 101} ()$，得到的仙力值 $K$ 为 $202\ 030\ 301\ 020\ 101$。

2. $(1,2,\underline{1},2,1) \xrightarrow{K=303} (1,\underline{2},\underline{2},1) \xrightarrow{K=3\ 030\ 203} (\underline{1},\underline{1}) \xrightarrow{K=30\ 302\ 030\ 102} ()$，得到的仙力值 $K$ 为 $30\ 302\ 030\ 102$。

子任务

对于所有测试数据，保证 $1 \le N \le 50$，$1 \le a_i \le N$。

测试点编号	$N\le$	特殊性质
$1\sim 2$	$18$	无
$3$	$50$	A
$4$		B
$5\sim 8$		C,D
$9\sim 12$		C
$13\sim 16$		D
$17\sim 25$		无

特殊性质 A：保证 $a_i=i$。

特殊性质 B：保证 $a_i=1$。

特殊性质 C：保证不存在 $p_1<p_2<p_3<p_4$，使得 $a_{p_1}=a_{p_3},a_{p_2}=a_{p_4},a_{p_1}\neq a_{p_2}$。

特殊性质 D：保证不存在 $p_1<p_2<p_3$，使得 $a_{p_1}=a_{p_2}=a_{p_3}$。