You will be given a binary array A of length N. (Array filled with 0s and/or 1s)
You need to divide the array in three parts (that is , three subarrays) in such a way that all these parts represent same value in decimal.
If it is possible to divide the array, output the common decimal value modulo 1000000007 else output -1.
See Sample test-case for better understanding.
Note - Here binary to decimal conversion is done using standard conversion method, i.e., right to left( Example - 1010 is 10 not 5).
Input format:
First line represents the number of test-cases T.
For each case:
First line represent the number N, size of the array.
Next line consists of N numbers either 0 or 1.
Output format:
For each case, output the required answer in new line.
Constraints:
1≤T≤10
3≤N≤105
0≤A[i]≤1
Hint: Think greedily.
In first case: array can be divided as: [1], [0 1], [0 1]. All these 3 parts represent common value '1' in decimal. Output 1
In second case: array cannot be divided in 3 parts such that they can have common value in decimal. Output -1.
