奇怪的棋盘

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

【题目描述】

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

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

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

【输入格式】

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

接下来一行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