You are given an array arr of length N, which contains only two values either 0  or 1.

You have to divide the array into maximum number of contiguous subarrays satisfying the following conditions:

• The first subarray should be of length 1. Next subsequent subarrays should have length 1 more than the length of the previous subarray.
• The count of distinct elements in any subarray should be 1.

To achieve the above conditions you can remove zero or more elements from the given array or rearrange the elements (if required). Let K be the maximum number of contiguous subarrays that can be formed from the given array satisfying the above conditions after removing (possibly 0) minimum possible elements.

Task

Determine the count of distinct obtainable arrangements of the given array such that it satisfies the given conditions and the number of subarrays in that arrangement should be exactly K.

Notes

• Let us understand the meaning of contiguous subarray with respect to this problem with an example. Suppose after removing minimum possible array elements you get an array of size 10. Now, you can rearrange the array elements and divide it into contiguous subarray, i.e. [ [1], [2, 3], [4, 5, 6], [7, 8, 9, 10] ]. Here 10 array elements are divided into 4 contiguous subarrays.
• Since the answer can be very large print answer modulo \(10^9+7\).

Example

Assumptions

• N = 4
• arr = [0, 1, 0, 1]

Approach

There are two possible ways to get the K = 2  maximum contiguous subarrays:

• [0, 1, 1]: Remove one 1 from arr and rearrange the elements. We can see it is divided into K = 2 as [[0], [1, 1]].
• [1, 0, 0]: Remove one 0 from arr and rearrange the elements. We can see it is divided into K = 2 as [[1], [0, 0]].

Thus, the answer is 2.

Function description

Complete the function solve provided in the editor. This function takes the following 2 parameters and returns the required answer:

• N: Represents the size of array arr
• arr: Represents the elements of array arr

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
• For each test case:
  • The first line contains N denoting the size of array arr.
  • The second line contains N space-separated value either 0 or 1, denoting the elements of arr.

Output format
For each test case, print the answer modulo \(10^9+7\)  in a new line.

Constraints
\(1 \leq T \leq 10\)
\(1 \leq N \le 10^5\)

\(arr_i \in \{0, 1\} \space \forall \space i\in[1, N]\)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.