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 \le T \le 10\)

\(3 \le N \le 10^5\)

\(0 \le A[i] \le 1\)

 

Hint: Think greedily.