Problem Background

If there were no gods in the world, this would be the realm of humans.

Problem Description

You are to preside over a ritual that involves \( N \) jade stones arranged in a row, numbered from left to right as \( 1, 2, \cdots, N \). The color of the \( i \)-th stone is \( a_i \).

During each round of the ritual, you need to select a segment of stones with the same color \( a_l \sim a_r \) (where \( 1 \le l \le r \le N \le 50 \)) and submerge them into the water. The ritual's spiritual power value \( K \) will then be updated to \( 10000 \cdot K + 100 \cdot l + r \), with \( K \) initially being \( 0 \).

After a segment of stones is submerged, the stones to the right will shift leftward. Additionally, their numbering will change to be sequentially numbered from left to right as \( 1, 2, \cdots \). For example, if there are \( 7 \) stones with colors \( 1, 1, 2, 2, 2, 3, 2 \), initially, the stone with color \( 3 \) is numbered \( 6 \). After stones \( 3 \sim 5 \) are submerged, its number will become \( 3 \).

When all stones are submerged, the ritual is complete, and the final spiritual power value is the result of this ritual. How many different spiritual power values can be obtained upon completion of the ritual?

Since the answer may be very large, output the answer modulo \( 10^9 + 7 \).

Input Format

The input consists of two lines.

The first line contains a single 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 stone.

Output Format

Output a single integer, which is the number of different spiritual power values modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

1
1

Sample Output #1

1

Sample Input #2

3
3 3 1

Sample Output #2

8

Sample Input #3

5
1 2 1 2 1

Sample Output #3

165

Sample Input #4

See the file in the contestant's directory under jade/jade4.in and jade/jade4.ans.

Sample Output #4

This sample meets the constraints of test points 5 ∼ 8.

Sample Input #5

See the file in the contestant's directory under jade/jade5.in and jade/jade5.ans.

Sample Output #5

This sample meets the constraints of test points 9 ∼ 12.

Sample Input #6

See the file in the contestant's directory under jade/jade6.in and jade/jade6.ans.

Sample Output #6

This sample meets the constraints of test points 13 ∼ 16.

Sample Input #7

See the file in the contestant's directory under jade/jade7.in and jade/jade7.ans.

Sample Output #7

Notes

Sample Explanation #3

Here are two possible spiritual power values and their methods of attainment:

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} ()\), resulting in a spiritual power value \( K \) of \( 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} ()\), resulting in a spiritual power value \( K \) of \( 30\ 302\ 030\ 102 \).

Subtasks

For all test data, it is guaranteed that \( 1 \le N \le 50 \) and \( 1 \le a_i \le N \).

Special Property A: \( a_i = i \).

Special Property B: \( a_i = 1 \).

Special Property C: There does not exist \( p_1 < p_2 < p_3 < p_4 \) such that \( a_{p_1} = a_{p_3}, a_{p_2} = a_{p_4}, a_{p_1} \neq a_{p_2} \).

Special Property D: There does not exist \( p_1 < p_2 < p_3 \) such that \( a_{p_1} = a_{p_2} = a_{p_3} \).

见题面 Input 部分

见题面 Output 部分