[湖北省选模拟 2024] 沉玉谷 / jade

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

你将主持一场祭祀，祭祀会使用到 $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$ | $50$ | B | | $5\sim 8$ | $50$ | C,D | | $9\sim 12$ | $50$ | C | | $13\sim 16$ | $50$ | D | | $17\sim 25$ | $50$ | 无 | 特殊性质 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}$。