Given an array A of n non-negative integers. Find the number of ways to partition/divide the array into subarrays, such that mex in each subarray is not more than k. For example, mex of the arrays [1, 2] will be 0, and that of [0, 2] will be 1, and that of [0, 1, 2] will be 3. Due to the fact that the answer can turn out to be quite large, calculate it modulo 109 + 7.

-----Input-----
- The first line of the input contains two integers n, k denoting the number of elements and limit of mex.
- The second line contains n space-separated integers A1, A2, ... , An .

-----Output-----
- Output a single integer corresponding to the answer of the problem.

-----Constraints-----
- 1 ≤ n ≤ 5 * 105
- 0 ≤ k, A[i] ≤ 109

-----Example-----
Input:
3 1
0 1 2

Output:
2

Input:
10 3
0 1 2 3 4 0 1 2 5 3

Output:
379

-----Explanation-----
Example 1. The valid ways of partitioning will be [[0], [1, 2]] (mex of first subarray is 1, while that of the second is zero), and [[0], [1], [2]] (mex of first subarray is 1, and that of others is 0). There is no other way to partition the array such that mex is less than or equal to 1. For example, [[0, 1], [2]] is not a valid partitioning as mex of first subarray is 2 which is more than 1.

见题面

见题面