题目描述

如图所示，给定一个由 $n$ 列组成的阶梯形网格，所有列的底部对齐。第 $i$ 列的高度为 $h_i$（即该列有 $h_i$ 个可用格子）。

你需要在网格中放入 $k$ 个完全相同的标记。放置规则：任意两个标记不得位于同一行，也不得位于同一列。

需要注意的是，若两个标记位于同一行号，但中间隔着不存在的格子（即某列高度不够），则不算冲突。

例如，上图中若标记 b 的两个位置在同一列，则不合法。但标记 a 的两个位置虽然行号相同，中间被短列隔断，所以是合法的。

请求出所有合法放置方案的总数，结果对 $10^9+7$ 取模。

输入格式

输入第一行两个整数 $n$ 和 $k$，分别表示网格的列数和需要放置的标记数量。

第二行包含 $n$ 个正整数 $h_1, h_2, \cdots, h_n$，依次表示从左到右每一列的高度。

输出格式

输出一行一个整数，表示合法放置方案的总数，对 $10^9+7$ 取模。

样例

3 3
2 1 3

2

4 1
1 2 3 4

10

5 2
2 3 1 2 4

43

3 2
999999 999999 999999

990979013

提示

数据规模与约定

• 对于 $40\%$ 的数据，所有列的高度均小于 $15$；
• 对于 $70\%$ 的数据，所有列的高度均小于 $100$；
• 对于 $100\%$ 的数据，$1\le n,k\le 500$，列高不超过 $10^6$。