Solve the programming task below in a Python markdown code block.
Kulyash has given you an array A of size N. 

He defines the *subsequence-number* of a non-empty [subsequence] 
S of array A as the number formed by the concatenation of all the elements of the subsequence S. 

Find the count of non-empty subsequences of A having their *subsequence-numbers* divisible by 7. Since the answer can be huge, output it modulo 10^{9} + 7.

For example: Consider A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. A subsequence S of A is [2, 5, 7, 10]. The *subsequence-number* of this subsequence is 25710.

------ Input Format ------ 

- The first line will contain T, the number of test cases. Then the test cases follow.
- The first line of each test case contains one integer N, the size of the array.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — the elements of the array A.

------ Output Format ------ 

For each test case, output in a single line the number of subsequences with *subsequence-number* divisible by 7 modulo 1000000007.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 3\cdot 10^{5}$
$1 ≤ A_{i} ≤ 3\cdot 10^{5}$
- Sum of $N$ over all test cases does not exceed $3\cdot 10^{5}$

----- Sample Input 1 ------ 
3
2
1 2
4
1 2 3 4
2
7 7

----- Sample Output 1 ------ 
0
1
3

----- explanation 1 ------ 
Test case $1$: Only $3$ subsequences are possible for the given array. These are $[1]$, $[1, 2]$, and $[2]$. The *subsequence-numbers* are $1$, $12$, and $2$ respectively. None of the *subsequence-numbers* are divisible by $7$, so the answer is $0$.

Test case $2$: $[1, 4]$ is the only subsequence having its *subsequence-number* $14$ which is divisible by $7$. So, the answer is $1$.

Test case $3$: All the non-empty subsequences $[7]$, $[7]$, and $[7, 7]$ have their *subsequence-numbers* $7, 7,$ and $77$ divisible by $7$. So, the answer is $3$.