Milk

题目描述

我们在羊水中漫步

脑海中装满的话 脱口而出净是泡沫

我看不到 我看不到 分离凝乳指尖

我听不到 我听不到 沸腾消失不见

—— 奶水

给定一个长度为 $n$ 的序列 $a_i$。 令 $f(a)$ 如下计算：

• $f(a)$ 初始值为 $0$。
• 选择一个区间 $[l,r]$，满足 $\forall i\in[l,r],a_i=a_l$，并将这个区间删去，使 $f(a)$ 改变为 $10^4\times f(a)+10^2\times l+r$。
• 删去后右侧的序列向左边移动，编号同时发生变化。
• 以此类推，直到序列为空。

$f(a)$ 随选择区间的不同会有变化，试问可以产生多少种不同的 $f(a)$？这个数字可能很大，对 $10^9+7$ 取模后输出。

输入格式

第一行两个正整数 $n,sid$，其中 $sid$ 表示子任务编号，样例的 $sid=0$。

接下来一行 $n$ 个整数 $a_i$。

输出格式

仅一行一个整数表示不同 $f(a)$ 的个数。

样例

样例 1

1 0
1

1

样例 2

3 0
3 3 1

8

样例 3

5 0
1 2 1 2 1

165

样例 4

见附加文件 milk4.in/milk4.out，该组数据满足 Subtask 4 的特殊限制。

样例 5

见附加文件 milk5.in/milk5.out，该组数据满足 Subtask 5 的特殊限制。

样例 6

见附加文件 milk6.in/milk6.out，该组数据满足 Subtask 6 的特殊限制。

样例 7

见附加文件 milk7.in/milk7.out。

数据范围

对于所有数据，满足 $1\le n\le 50$，$1\le a_i\le n$。

特殊性质 A：不存在 $i<j<k<l$，使得 $a_i=a_k,a_j=a_l,a_i\not=a_j$。

特殊性质 B：不存在 $i<j<k$，使得 $a_i=a_j=a_k$。