SP3734 PERIODNI - Periodni

Luka 在化学课上感到无聊，所以他盯着挂在黑板上方墙上的一张大型化学元素周期表看。为了打发时间，Luka 决定做一张完全不同于课堂上的属于自己的表格。 他的表格有 $N$ 列，每列有不同的高度，底部对齐（见下例）。画完表格后，他需要在表格里放一些元素。他首先决定放入 $K$ 种稀有气体。Luka 必须把它们放到表格中，确保没有两个稀有气体相靠近。 如果表格中的两个方格位于同一列或同一行，并且它们之间的所有方格都存在，那么它们就是彼此靠近。在下面的例子中，`a` 方格不靠近，但 `b` 方格是靠近的。  写一个程序，给定 $N$、$K$ 以及 $N$ 列的高度，计算 Luka 将稀有气体放入表格的总方法数。这个数字可能很大，所以输出结果对 $10^9+7$ 取模。

第一行包含两个整数 $N$ 和 $K$（$1 \leq N \leq 500$，$1 \leq K \leq 500$），以空格分隔，分别表示 Luka 表格中的列数以及稀有气体的数量。 下一行包含 $N$ 个正整数，以空格分隔。这些是从左到右的柱子高度，高度最多为 $10^6$。

输出 Luka 用稀有气体填充他的表格的方法数量，对 $10^9+7$ 取模。