Luka 在化学课上感到很无聊，于是他盯着黑板上方墙上挂着的一张巨大的化学元素周期表。为了消磨时间，Luka 决定制作一张与教室里那张完全不同的自己的周期表。

他的表由 $N$ 列组成，每列都有一定的高度，且底部对齐（见下图）。

画好表后，他需要往里面填入元素。他首先决定填入稀有气体，一共有 $K$ 个。Luka 必须将它们放入表中，使得任意两个稀有气体互不相邻。

如果表中的两个方格位于同一列或同一行，并且它们之间的所有方格都存在，则称这两个方格是相邻的。在下面的例子中，标有 'a' 的方格不相邻，而标有 'b' 的方格相邻。

编写一个程序，在给定 $N$、$K$ 以及这 $N$ 列的高度的情况下，计算 Luka 将稀有气体放入表中的总方案数。由于这个数字可能很大，请将其对 $1000000007$ 取模后输出。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $K$（$1 \le N \le 500$，$1 \le K \le 500$），分别表示 Luka 的表中的列数和稀有气体的数量。

第二行包含 $N$ 个空格分隔的正整数，表示从左到右各列的高度。高度最大为 $1\,000\,000$。

输出格式

输出 Luka 将稀有气体填入表中的方案数，对 $1000000007$ 取模。

子任务

对于占总分 $40\%$ 的测试数据，输入中的所有数字都小于 $15$。

对于占总分 $70\%$ 的测试数据，输入中的所有数字都小于 $100$。

样例

输入样例 1

3 3
2 1 3

输出样例 1

2

输入样例 2

4 1
1 2 3 4

输出样例 2

10

输入样例 3

5 2
2 3 1 2 4

输出样例 3

43

输入样例 4

3 2
999999 999999 999999

输出样例 4

990979013