You are given an array A of length N and it contains only 0 or 1 i.e a binary array.You task is to divide the array in three parts i.e three subarrays such that all these parts represent same value in base 10. If it is possible to divide the array, output the common decimal(base 10) 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 :

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 :

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$