Background

If there were no gods under heaven, this would be the kingdom of humans.

Problem Description

You will preside over a ritual. The ritual uses $N$ jade stones arranged in a line, numbered from left to right as $1,2,\cdots,N$. The color of jade stone $i$ is $a_i$.

In each round of the ritual, you need to choose a consecutive segment of jade stones with the same color $a_l \sim a_r(1\le l \le r\le N\le 50)$, and sink them into the water. The immortal power value $K$ of this ritual will become $10000\cdot K+100\cdot l+r$, where the initial value of $K$ is $0$.

After a segment of jade stones is sunk into the water, the jade stones on the right will shift left. At the same time, the numbering will also change, and they will be renumbered from left to right as $1,2,\cdots$. For example, there are $7$ jade stones with colors $1,1,2,2,2,3,2$. At the beginning, the jade stone with color $3$ is numbered $6$. After jade stones $3\sim 5$ are sunk into the water, its number will become $3$.

When all jade stones have been sunk into the water, the ritual is completed, and the value of $K$ at this time is the immortal power value of this ritual. How many different immortal power values are possible after the ritual is completed?

Since the answer may be very large, you only need to output the value modulo $10^9+7$.

Input Format

The input has two lines.

The first line contains a positive integer $N$, representing the number of jade stones.

The second line contains $N$ positive integers $a_1,a_2,\cdots,a_N$, where $a_i$ represents the color of the $i$-th jade stone.

Output Format

Output one line with one integer, representing the number of different immortal power values modulo $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。

Hint

Sample Explanation 3

Here are two possible immortal power values and the ways to obtain them:

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} ()$, obtaining the immortal power value $K$ as $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} ()$, obtaining the immortal power value $K$ as $30\ 302\ 030\ 102$.

Subtasks

For all testdata, it is guaranteed that $1 \le N \le 50$ and $1 \le a_i \le N$.

Special Property A: It is guaranteed that $a_i=i$.

Special Property B: It is guaranteed that $a_i=1$.

Special Property C: It is guaranteed that there do not exist $p_1<p_2<p_3<p_4$ such that $a_{p_1}=a_{p_3}$, $a_{p_2}=a_{p_4}$, and $a_{p_1}\neq a_{p_2}$.

Special Property D: It is guaranteed that there do not exist $p_1<p_2<p_3$ such that $a_{p_1}=a_{p_2}=a_{p_3}$.

Translated by ChatGPT 5