P6453 [/2009 #4] PERIODNI

题目描述

如图，给定一个由 $n$ 列组成的表格，每一列的底部都是对齐的。

你需要再里面填入 $k$ 个相同的数。但不得有任意两个数在同一行或者同一列。

比如，上图中 b 的填写就是不合法的；因为两个 b 在同一列上。但 a 的填写是合法的，因为这两个 a 虽然在同一行，但是中间断开了，所以不算做非法。

请求出填写的方案总数 $\bmod\ 10^9+7$ 的结果。

输入格式

输入第一行两个整数 $n,k$，表示表格的列数和相同数字的数量。

第二行包含 $n$ 个整数，第 $i$ 个整数表示从左至右第 $i$ 列的层数。

输出格式

输出一行一个整数，表示方案总数 $\bmod\ 10^9+7$ 的结果。

输入输出样例 #1

输入 #1

3 3
2 1 3

输出 #1

2

输入输出样例 #2

输入 #2

4 1
1 2 3 4

输出 #2

10

输入输出样例 #3

输入 #3

5 2
2 3 1 2 4

输出 #3

43

输入输出样例 #4

输入 #4

3 2
999999 999999 999999

输出 #4

990979013

说明/提示

数据规模与约定

• 对于 $40\%$ 的数据，输入的数字都小于 $15$；
• 对于 $70\%$ 的数据，输入的数字都小于 $100$；
• 对于 $100\%$ 的数据，$1\le n,k\le 500$，层高不会超过 $10^6$。