SPOJ PERIODNI

有一块由 $N$ 个从左到右相邻且底端对齐的竖直列组成的棋盘。第 $i$ 列包含 $h_i$ 个单位方格。第 $i$ 列从底部起第 $y$ 行的方格存在，当且仅当 $1\le y\le h_i$。

现在要在棋盘中恰好放置 $K$ 个车，且每个方格至多放置一个车。车只能沿棋盘中连续存在的方格横向或纵向攻击，不能越过不存在的方格。

等价地，位于 $(i,y)$ 和 $(j,z)$ 的两辆车互相攻击，当且仅当满足以下条件之一：

• $i=j$；
• $y=z$，并且对于 $i$ 与 $j$ 之间（含端点）的每一列 $t$，均有 $h_t\ge y$。

求有多少种放置方案，使任意两辆车都不互相攻击。两个方案不同，当且仅当至少有一个方格只在其中一个方案中放置了车。

答案对 $10^9+7$ 取模。

输入格式

第一行包含两个正整数 $N$ 和 $K$，分别表示棋盘的列数和需要放置的车数。

第二行包含 $N$ 个正整数 $h_1,h_2,\ldots,h_N$，表示棋盘中各列的高度。

输出格式

输出一个非负整数，表示满足条件的放置方案数对 $10^9+7$ 取模后的结果。

样例输入

5 2
2 3 1 2 4

样例输出

43

数据范围

• $N\le 500$；
• $K\le 500$；
• $h_i\le 10^6$。

来源与许可

本题题面与测试数据整理自 SPOJ PERIODNI 与 BZOJ。

样例 1

输入

5 2
2 3 1 2 4

输出

43