Every day the express train goes past the farm. It has \(N\) carriages
(\(1 \leq N \leq 10^5\)), each with a positive integer label between \(1\) and
\(10^9\); 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 \(c_1,\dots,c_{N+1-K}\), where \(c_i\) is the minimum label among
carriages \(i, i+1, \dots, 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 \(10^9 + 7\).

Bessie's information is completely reliable; that is, it is guaranteed that
there is at least one consistent way to assign labels.

Problem credits: Dhruv Rohatgi

Problem credits: Dhruv Rohatgi

The first line consists of two space-separated integers, \(N\) and \(K\). The
subsequent lines contain the sliding window minimums \(c_1,\dots,c_{N+1-K}\), one
per line.

A single integer: the number of ways, modulo \(10^9 + 7\), to assign a positive
integer not exceeding \(10^9\) to each carriage, such that the minimum label among
carriages \(i, i+1, \dots, i+K-1\) is \(c_i\) for each \(1 \leq i \leq N-K+1\).

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > January > Platinum