Train Car Numbering

A fast train with N cars (1 ≤ N ≤ 10⁵) passes by a farm each day. Each car is assigned a positive integer between 1 and 10⁹ (numbers may repeat). Normally, Bessie records the car numbers as they pass. However, due to thick fog today she couldn’t see any car numbers. Fortunately, she receives reliable information from the city: she is given an integer K and a list of N-K+1 positive integers c₁, c₂, …, c_N+1-K, where c_i is the minimum number among the cars in positions i, i+1, …, i+K-1.

Your task is to compute the number of ways to assign numbers to the N train cars in accordance with the sliding window minimum information. As the answer can be huge, output it modulo 10⁹+7.

It is guaranteed that the message is reliable – that is, there exists at least one valid numbering of the cars satisfying all the sliding window minimum constraints.

Note on the constraints:
For every sliding window from car i to car i+K-1, the following must hold:

• Every car in the window has a number which is at least c_i (i.e. a_j ≥ c_i for all j in [i, i+K-1]).
• At least one car in the window has the exact number c_i (so that the minimum is reached).

Hint: For each car position j (1-indexed), one may first deduce a lower bound L[j] defined as:

[ L[j] = \max{ c[i] : \max(1, j-K+1) \le i \le \min(j, N-K+1) }]

Then, one may show that if we force, in each sliding window, a specific position where the minimum occurs, the number of valid assignments is the product over all free (non‐forced) positions of the number of choices available (which is (10⁹ - L[j] + 1)). One way to force a position in the window starting at i is to choose the rightmost index in the interval [i, i+K-1] whose corresponding lower bound equals c_i.

inputFormat

The first line contains two space‐separated integers: N and K.

The next line contains N-K+1 space‐separated integers: c1 c2 … cN+1-K.

outputFormat

Print a single integer – the number of valid ways to assign a number to each of the N train cars, modulo 10⁹+7.

sample

3 2
3 4

999999997