## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Subsequence-Numbers Divisible by 7 CodeChef Solution | CodeChef Problem Solution 2022

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=\left[1,2,3,4,5,6,7,8,9,10\right]$. A subsequence $S$ of $A$ is $\left[2,5,7,10\right]$. 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},\dots ,{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\le T\le 1000$
• $1\le N\le 3\cdot {10}^{5}$
• $1\le {A}_{i}\le 3\cdot {10}^{5}$
• Sum of $N$ over all test cases does not exceed $3\cdot {10}^{5}$