/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は N 個のブロック塔を左から右に一列に並べて作ろうとしています。 i 番目のブロック塔の目標の高さは H_i 段です。
組み立ては 1 ステップに 1 個のブロックを積む作業で進みます。各ステップでは、まだ目標の高さに達していないブロック塔を 1 つ選び、その塔の上にブロックを 1 個載せます（高さが 1 増えます）。すべてのブロック塔は初期状態では高さ 0 であり、すべてのブロック塔が目標の高さに達したとき組み立ては完了です。
高橋君は、展示の見栄えを良くするため、次の条件を常に守る必要があります。
見栄え条件: 各ステップの直後において、ブロック塔の列を左端から眺めたときに「見える塔の本数」が K 本以上でなければならない。
ブロック塔の列を左端から眺めたとき、 i 番目の塔が「見える」とは、 i 番目の塔の現在の高さが 1 以上であり、かつ i より左にあるすべての塔の現在の高さよりも真に大きいことです。ただし i = 1 のときは、高さが 1 以上であれば見えるとします。
より厳密には、現在の各塔の高さを h_1, h_2, \ldots, h_N としたとき、塔 i が見えるとは、 h_i \geq 1 かつ h_i > \max(h_1, h_2, \ldots, h_{i-1}) を満たすことです（ただし i = 1 のときは h_1 \geq 1 であれば見えるとします）。
高橋君は、この見栄え条件を守りながら組み立てを完了できるかどうかを判定したいと考えています。さらに、完了できる場合は、条件を満たす作業手順が何通りあるかを求めたいです。
条件を満たしながらすべてのブロック塔を目標の高さまで積み上げることが可能ならば、そのような作業手順の総数を 10^9 + 7 で割った余りを出力してください。不可能ならば 0 を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq H_i \leq 10^6
- \sum_{i=1}^{N} H_i \leq 10^6
- 入力はすべて整数である
入力
N K H_1 H_2 \ldots H_N
- 1 行目には、ブロック塔の個数を表す N と、見栄え条件で必要な見える塔の最小本数を表す K が、スペース区切りで与えられる。
- 2 行目には、各ブロック塔の目標の高さを表す H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
出力
見栄え条件を満たしながらすべてのブロック塔を目標の高さまで組み立てる作業手順の総数を 10^9 + 7 で割った余りを 1 行で出力せよ。条件を満たす手順が存在しない場合は 0 を出力せよ。
入力例 1
3 1 1 2 1
出力例 1
12
入力例 2
4 2 1 1 1 1
出力例 2
0
入力例 3
8 1 3 1 4 2 5 2 1 3
出力例 3
821889649
入力例 4
20 1 12 7 25 18 3 30 11 6 22 14 9 27 5 16 20 8 24 13 10 19
出力例 4
85505878
入力例 5
1 1 1
出力例 5
1
Score : 400 pts
Problem Statement
Takahashi is trying to build N block towers lined up in a row from left to right. The target height of the i-th block tower is H_i blocks.
The construction proceeds in steps, where one block is stacked in each step. In each step, Takahashi chooses one block tower that has not yet reached its target height, and places one block on top of it (increasing its height by 1). Initially, all block towers have a height of 0. The construction is complete when all block towers have reached their target heights.
To make the exhibition look good, Takahashi must always satisfy the following condition:
Appearance Condition: Immediately after each step, when looking at the row of block towers from the left end, the "number of visible towers" must be at least K.
When looking at the row of block towers from the left end, the i-th tower is "visible" if its current height is at least 1, and it is strictly greater than the current heights of all towers to its left. For i = 1, it is visible if its height is at least 1.
More precisely, letting h_1, h_2, \ldots, h_N be the current heights of the towers, tower i is visible if h_i \geq 1 and h_i > \max(h_1, h_2, \ldots, h_{i-1}) (for i = 1, it is visible if h_1 \geq 1).
Takahashi wants to determine whether it is possible to complete the construction while satisfying this appearance condition. Furthermore, if it is possible, he wants to find the number of valid construction procedures (sequences of steps).
If it is possible to stack all block towers to their target heights while satisfying the condition, output the total number of such construction procedures modulo 10^9 + 7. If it is impossible, output 0.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq H_i \leq 10^6
- \sum_{i=1}^{N} H_i \leq 10^6
- All input values are integers.
Input
N K H_1 H_2 \ldots H_N
- The first line contains N, the number of block towers, and K, the minimum number of visible towers required by the appearance condition, separated by a space.
- The second line contains H_1, H_2, \ldots, H_N, the target heights of each block tower, separated by a space.
Output
Print the total number of construction procedures to build all block towers to their target heights while satisfying the appearance condition, modulo 10^9 + 7, in a single line. If no such procedure exists, print 0.
Sample Input 1
3 1 1 2 1
Sample Output 1
12
Sample Input 2
4 2 1 1 1 1
Sample Output 2
0
Sample Input 3
8 1 3 1 4 2 5 2 1 3
Sample Output 3
821889649
Sample Input 4
20 1 12 7 25 18 3 30 11 6 22 14 9 27 5 16 20 8 24 13 10 19
Sample Output 4
85505878
Sample Input 5
1 1 1
Sample Output 5
1