Intuit OA 2023 - Playing With 0's and 1's

Alice is playing with numbers 0's and 1's. She decided to count the number of subarrays which satisfy the following condition:
Ratio of number of 0's to number of 1's is X:Y. She starts struggling as soon as the count of numbers increases. Can you help her find the solution to this problem?

Input Format

• The first line contains N, the count of numbers. The numbers contain only 0's and 1's.
• The second line contains N space-separated integers (0 or 1).
• The third line contains 2 space-separated integers X and Y.

Output Format

Print the count of subarrays which have 0's and 1's in the ratio of X:Y. Output the answer modulo ((10^9+7)).

Constraints

• (1 <= N <= 10^5)
• (1 <= X <= 10^5)
• (1 <= Y <= 10^5)

Example

Sample Input:

4
0 1 0 1
1 1

Sample Output:

4

Explanation:

The valid subarrays where the ratio of 0's to 1's is 1:1 are:

1. ([01])
2. (0 [10] 1)
3. (01 [01])
4. ([0 1 0 1])

Thus, the output is 4.