Background

USACO January 2019 Contest, Platinum Problem 3.

Problem Description

Every day, an express train passes by the farm. The train has $N$ cars ($1 \le N \le 10^5$). Each car has a positive integer label between $1$ and $10^9$; different cars may have the same label.

Normally, Bessie watches the passing train and records the labels on the cars. But today the fog is so thick that Bessie cannot see a single label. Luckily, she learned from a reliable source in the city the minimum values of all sliding windows of the label sequence. Specifically, she is given a positive integer $K$, and $N-K+1$ positive integers $c_1,\ldots,c_{N+1-K}$, where $c_i$ is the minimum label among cars $i,i+1,\ldots,i+K-1$.

Help Bessie find the number of ways to assign labels to all cars such that all the sliding-window minimum values match. Since this number may be very large, output it modulo $10^9+7$.

Bessie's information is completely reliable; in other words, it is guaranteed that there exists at least one valid labeling.

Input Format

The first line contains two space-separated integers $N$ and $K$. The remaining lines contain all sliding-window minimum values $c_1,\ldots,c_{N+1-K}$, one number per line.

Output Format

Output one integer: the number of ways to assign each car a positive integer label not exceeding $10^9$, modulo $10^9+7$, such that the minimum label among cars $i,i+1,\ldots,i+K-1$ equals $c_i$, for all $1 \le i \le N-K+1$.

4 2
999999998
999999999
999999998

3

Hint

Translated by ChatGPT 5