기차 추적 2

매일 특급열차가 농장 옆을 지나간다. 열차에는 $N$개의 객차($1 \leq N \leq 10^5$)가 있고, 각 객차에는 $1$ 이상 $10^9$ 이하의 양의 정수 번호가 붙어 있다. 서로 다른 객차에 같은 번호가 붙어 있을 수도 있다.

평소라면 Bessie는 열차가 지나가는 것을 보며 객차 번호를 기록한다. 하지만 오늘은 안개가 너무 짙어서 번호를 하나도 볼 수 없다. 다행히 Bessie는 도시의 믿을 만한 곳에서 객차 번호 수열의 슬라이딩 윈도우 최솟값을 구해 두었다. 양의 정수 $K$와 $N-K+1$개의 양의 정수 $c_1,\dots,c_{N+1-K}$가 있으며, $c_i$는 객차 $i, i+1, \dots, i+K-1$ 중 번호의 최솟값이다.

Bessie를 도와 슬라이딩 윈도우 최솟값과 맞아떨어지도록 각 객차에 번호를 붙이는 방법의 수를 구하라. 이 수는 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다.

Bessie의 정보는 완전히 신뢰할 수 있다. 맞아떨어지는 배정이 적어도 하나는 존재한다는 것이 보장된다.

첫째 줄에 공백으로 구분된 두 정수 $N$과 $K$가 주어진다. 이어지는 줄에는 슬라이딩 윈도우 최솟값 $c_1,\dots,c_{N+1-K}$가 한 줄에 하나씩 주어진다.

하나의 정수를 출력한다. 각 객차에 $10^9$ 이하의 양의 정수를 배정하는 방법 중, 모든 $1 \leq i \leq N-K+1$에 대해 객차 $i, i+1, \dots, i+K-1$ 중 번호의 최솟값이 $c_i$가 되는 방법의 수를 $10^9 + 7$로 나눈 나머지이다.