题目描述

输入格式

第一行包括两个正整数 $N$ 和 $K$，表示了棋盘的列数和放的车数。 第二行包含 $N$ 个正整数，表示了棋盘每列的高度。

输出格式

包括一个非负整数，表示有多少种放置的方案，输出答案$\mod 1000000007$ 后的结果即可。

示例

输入1

5 2 
2 3 1 2 4

输出1

43

提示

对于 $100\%$ 的数据，有 $N \leq 500$，$K \leq 500$，$h_i \leq 1000000$。