7 人解决，12 人已尝试。
9 份提交通过，共有 21 份提交。
6.8 EMB 奖励。
3438. 棋盘上的車
单点时限: 2.0 sec
内存限制: 256 MB
给定一张形如条形图的国际象棋棋盘，这张棋盘由 $n$ 条高度可能不相等的列组成，但保证所有列的底边都是处于同一水平线上的。如图：
现在需要在棋盘上挑选 $k$ 个格子放置彼此不攻击的车，请问有多少种方法？输出方案数模 $10^9+7$ 的余数。所谓不攻击，就是说任意两只车不能通过棋盘上连续的一行或一列格子直接连在一起。如图中两个 $b$ 是可以相互攻击的，应避免这样放置；但两个 $a$ 是攻击不到的，因为中间一段越出了棋盘的边界。
输入格式
第一行为两个整数 $n$ 和 $k$，表示列的数量和需要放置的车的数量。
接下来一行有 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 列的高度 $h_i$。
- 对于 $40\%$ 的数据，满足 $1 \le n,k,h_i \le 15$
- 对于 $70\%$ 的数据，满足 $1 \le n,k,h_i \le 100$
- 对于 $100\%$ 的数据，满足 $1 \le n,k \le 500, 1 \le h_i \le 1~000~000$
输出格式
输出一个数表示方案总数模 $10^9+7$ 的余数。
样例
Input
3 3 2 1 3
Output
2
Input
4 1 1 2 3 4
Output
10
Input
5 2 2 3 1 2 4
Output
43
Input
3 2 999999 999999 999999
Output
990979013