题目描述

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

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

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

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

输入格式

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

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

输出格式

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

3 3
2 1 3

2

4 1
1 2 3 4

10

5 2
2 3 1 2 4

43

3 2
999999 999999 999999

990979013

提示

数据规模与约定

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

说明

题目译自 COCI2008-2009 CONTEST #4 T6 PERIODNI。