2019 USACO January
Train Tracking 2
Every day the express train goes past the farm. It has n carriages, each with a positive integer label between 1 and
109, different carriages may have the same label.
Usually, Bessie watches the train go by, tracking the carriage labels. But today is too foggy, and Bessie can't see any of the labels! Luckily, she has acquired the sliding window minimums of the sequence of carriage labels, from a reputable source in the city. In particular, she has a positive integer k, and n − k + 1 positive integers
cn + 1 − k, where
ci is the minimum label among carriages i, i + 1,..., i + k − 1.
Help Bessie figure out the number of ways to assign a label to each carriage, consistent with the sliding window minimums. Since this number may be very large, Bessie will be satisfied if you find its remainder modulo
109 + 7.
Bessie's information is completely reliable; that is, it is guaranteed that there is at least one consistent way to assign labels.
The first line consists of two space-separated integers n (1 ≤ n ≤
105) and k. The subsequent lines contain the sliding window minimums
cn + 1 − k, one per line.
Print a single integer: the number of ways, modulo
109 + 7, to assign a positive integer not exceeding
109 to each carriage, such that the minimum label among carriages i, i + 1, ..., i + k − 1 is
ci for each 1 ≤ i ≤ n − k + 1.
4 2 999999998 999999999 999999998