Sacrificial Jade Stones

We are given $N$ jade stones arranged in a row and numbered $1,2,\dots,N$. Each stone $i$ has a color $a_i$. In each round of the sacrificial ritual you must choose a contiguous segment $[l, r]$ (with $1\le l\le r\le N$) such that all the stones in that segment have the same color, and submerge them in water. When you submerge a segment, the mystical power $K$ is updated as follows: [ K \leftarrow 10000\cdot K + (100\cdot l + r), ] with an initial value of $K=0$. After submerging a segment, the stones on the right shift to the left and are renumbered consecutively starting from $1$. When all stones have been submerged the ritual is complete, and the final value of $K$ is recorded.

Your task is to determine the number of distinct final mystical power values that can be obtained by performing the removals in different orders. Two removal orders are considered different if the ordered sequence of chosen segments (that is, the $l$ and $r$ in each removal on the current numbering) differs. Since the answer might be large, output it modulo $10^9+7$.

Note: Although the update rule for $K$ may look like it accumulates digits in base $10000$, different orders of removal (even if they yield the same sequence of removed segments as numbers) are counted only once if the final value of $K$ is numerically equal.

inputFormat

The first line contains a single integer $N$ ($1 \le N \le 50$).\nThe second line contains $N$ integers $a_1,a_2,\dots,a_N$, where $a_i$ is the color of the $i$-th jade stone.

outputFormat

Output a single integer representing the number of distinct final mystical power values modulo $10^9+7$.

sample

1
1

1