题目背景

USACO 19年一月月赛铂金组第三题

题目描述

每天特快列车都会经过农场。列车有N节车厢（1≤N≤10^5），每节车厢上有一个1到10^9之间的正整数编号；不同的车厢可能会有相同的编号。 平时，Bessie会观察驶过的列车，记录车厢的编号。但是今天雾实在太浓了，Bessie一个编号也看不见！幸运的是，她从城市里某个可靠的信息源获知了列车编号序列的所有滑动窗口中的最小值。具体地说，她得到了一个正整数K，以及N−K+1个正整数c1,…,cN+1−K，其中ci是车厢i,i+1,…,i+K−1之中编号的最小值。

帮助Bessie求出满足所有滑动窗口最小值的对每节车厢进行编号的方法数量。由于这个数字可能非常大，只要你求出这个数字对10^9+7取余的结果Bessie就满意了。

Bessie的消息是完全可靠的；也就是说，保证存在至少一种符合要求的编号方式。

输入格式

输入的第一行包含两个空格分隔的整数N和K。余下的行包含所有的滑动窗口最小值c1,…,cN+1−K，每行一个数。

输出格式

输出一个整数：对每节车厢给予一个不超过109的正整数编号的方法数量对10^9+7取余的结果，满足车厢i,i+1,…,i+K−1之中编号的最小值等于ci，对于1≤i≤N−K+1均成立。

样例 #1

样例输入 #1

4 2
999999998
999999999
999999998

样例输出 #1

3