[USACO19JAN] Train Tracking 2 P

USACO 2019 一月月赛铂金组第三题

每天特快列车都会经过农场。列车有 $N$ 节车厢（$1 \le N \le 10^5$），每节车厢上有一个 $1$ 到 $10^9$ 之间的正整数编号；不同的车厢可能会有相同的编号。 平时，Bessie 会观察驶过的列车，记录车厢的编号。但是今天雾实在太浓了，Bessie 一个编号也看不见！幸运的是，她从城市里某个可靠的信息源获知了列车编号序列的所有滑动窗口中的最小值。具体地说，她得到了一个正整数 $K$ ，以及 $N-K+1$ 个正整数 $c_1,…,c_{N+1-K}$ ，其中 $c_i$ 是车厢 $i,i+1,…,i+K-1$ 之中编号的最小值。 帮助 Bessie 求出满足所有滑动窗口最小值的对每节车厢进行编号的方法数量。由于这个数字可能非常大，只要你求出这个数字对 $10^9+7$ 取余的结果 Bessie 就满意了。 Bessie 的消息是完全可靠的；也就是说，保证存在至少一种符合要求的编号方式。

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

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

4 2
999999998
999999999
999999998

3