All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
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.
- 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 a single integer corresponding to the answer of the problem.
- 1 ≤ n ≤ 5 * 105
- 0 ≤ k, A[i] ≤ 109
Input: 3 1 0 1 2 Output: 2
Input: 10 3 0 1 2 3 4 0 1 2 5 3 Output: 379
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], , [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.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.