奇怪的棋盘

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 boarda.in 输出文件 boarda.out

【题目描述】

现在有一张n列的棋盘，每一列的高度为h_i，每一列的底在同一水平线上。

然后你需要在这个棋盘上放k个象棋里的车，使得他们互不攻击，问一共有多少种不同的摆放方法。注意两个车可以互相攻击当且仅当他们处在同一行或者同一列，而且中间的棋盘没有空缺。

上图是一张合法的棋盘，每列高度分别为2，3，1，2，4，而且两个b可以互相攻击，但是a不会互相攻击。

【输入格式】

第一行两个整数，n和k，分别表示棋盘列数和需要放的车的个数

接下来一行n个正整数h_i，表示每一列的高度

【输出格式】

一行一个整数，表示方案数。结果对1000000007取模

【样例输入1】

3 3

2 1 3

【样例输出1】

2

【样例输入2】

5 2

2 3 1 2 4

【样例输出2】

43

【数据范围】

对于40%的数据，0 <= n,k,h_i <= 15

对于70%的数据，0 <= n,k,h_i <= 100

对于100%的数据，0 <= n, k <= 500, 0 <= h_i <= 1000000

【时限】

2s