题目描述

Luka 画了一张特殊表格，共有 $N$ 列，每列从底部对齐，但高度可能不同。

他要在其中放置 $K$ 个相同的“稀有气体”标记，并要求任意两个标记都不能“靠得太近”。

两个格子被认为“靠近”，当且仅当：

• 它们位于同一列；或
• 它们位于同一行，并且这两个格子之间的所有格子都存在。

因此，同一行中如果中间因为某列高度不足而出现断层，则断层两侧的两个格子并不算靠近。

求放置 $K$ 个标记的方案数，答案对 $1\,000\,000\,007$ 取模。

输入格式

第一行两个整数 $N,K$：

第二行 $N$ 个正整数 $H_1,H_2,\dots,H_N$，表示每列高度：

输出格式

输出一个整数，表示合法放置方案数对 $1\,000\,000\,007$ 取模后的结果。

样例

5 2
2 3 1 2 4

43

原题示意图