Number of ways (Hard version)

Number of ways (Hard version)

Time Limit: 2.0 s

Memory Limit: 128.0 MB

Description

You are given a binary array \(A[]\) and the length of the array is N. Binary array means this array element contains either 0 or 1.
You are also given a non-negative integer K.

  • You need to remove some element (at least one or possibly all) from the array such way that, total sum of remaining element is greater than or equal to K.

Find the total number of ways you can remove some element from the array A[], after the remaining element total sum is greater than or equal to K.

The answer can be very large, so print it modulo by \(10^9+7\).
Note : An empty array A[] total sum is 0.

The only difference between the hard and easy versions is the limit of N.

Input

First line T, the number of test cases.
In each test case, first line N the length of array and a non-negative integer K.
Second line, an array \(A[]\) with exactly N elements.

\(1<=T<= 10^3\)
\(1<= N <= 2 * 10^5 \)
\(0<= K<= 10^6\)
\(A[] = 0 , 1 \)

Sum of N overall test case doesn't exceed \(2 * 10^5\)

Output

In each test case, print the total number of ways modulo by \(10^9 + 7 \)

Sample

Input Output
2
3 1
1 0 1
3 1
1 1 1
5
6

First test case:
First test case

Information

ID
1094
Difficulty
5
Category
Combinatorics Click to Show
Tags
# Submissions
26
Accepted
12
Accepted Ratio
46%
Uploaded By

Related

In following contests:

Brain Booster #5