每天都有快车经过农场。列车共有 $N$ 节车厢（$1 \leq N \leq 10^5$），每节车厢都有一个 $1$ 到 $10^9$ 之间的正整数标签；不同的车厢可能有相同的标签。

通常，Bessie 会观察经过的列车，记录车厢的标签。但今天雾太大了，Bessie 看不清任何标签！幸运的是，她从城里一位可靠的消息来源那里获得了该车厢标签序列的滑动窗口最小值。具体来说，她得到了一个正整数 $K$ 以及 $N-K+1$ 个正整数 $c_1, \dots, c_{N+1-K}$，其中 $c_i$ 是第 $i$ 到第 $i+K-1$ 节车厢标签中的最小值。

请帮助 Bessie 计算出有多少种分配车厢标签的方法，使其与滑动窗口最小值相符。由于这个数字可能非常大，你只需要输出其对 $10^9 + 7$ 取模后的结果。

Bessie 获得的信息是完全可靠的；也就是说，保证至少存在一种符合条件的标签分配方案。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $K$。接下来的行包含滑动窗口最小值 $c_1, \dots, c_{N+1-K}$，每行一个。

输出格式

一个整数：符合条件的标签分配方案数，对 $10^9 + 7$ 取模。每节车厢的标签必须是不超过 $10^9$ 的正整数，且对于每个 $1 \leq i \leq N-K+1$，第 $i$ 到第 $i+K-1$ 节车厢的最小标签必须为 $c_i$。

样例

样例输入 1

4 2
999999998
999999999
999999998

样例输出 1

3

题目来源：Dhruv Rohatgi