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$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics


Solutions:
from bisect import bisect_right as bl
from random import randint as R
RI = lambda : [int(_x) for _x in input().split()]
II = lambda : int(input())
import random
mod = 10 ** 9 + 7
for _ in range(II()):
	n = II()
	A = RI()
	dp = [0] * 7
	dp[0] = 1
	for i in A:
		ndp = dp[:]
		le = len(str(i))
		rem = i % 7
		for j in range(7):
			ndp[(j * 10 ** le + rem) % 7] += dp[j]
		for j in range(7):
			ndp[j] %= mod
		dp = ndp[:]
	print((dp[0] - 1) % mod)


M = int(1000000000.0 + 7)
for q in range(int(input())):
	n = int(input())
	t = list(map(int, input().split()))
	dp = [[0] * 7 for _ in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		p = 10 ** len(str(t[i]))
		for j in range(7):
			k = (j * p + t[i]) % 7
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % M
			dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % M
	print((dp[-1][0] - 1 + M) % M)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dp = [[0 for i in range(n)] for j in range(7)]
	M = 1000000007
	for i in range(n):
		if i == 0:
			p = l[i] % 7
			dp[p][i] += 1
		else:
			for j in range(7):
				dp[j][i] += dp[j][i - 1]
				dp[j][i] %= M
			p = l[i] % 7
			dp[p][i] += 1
			for j in range(7):
				dp[(j * 10 ** len(str(l[i])) + l[i]) % 7][i] += dp[j][i - 1]
				dp[(j * 10 ** len(str(l[i])) + l[i]) % 7][i] %= M
	print(dp[0][n - 1])


import math
T = int(input())

def countDigit(n):
	return math.floor(math.log10(n) + 1)

def update(arr, a):
	one = [0] * 7
	for (i, x) in enumerate(arr):
		one[(i * 10 ** countDigit(a) + a) % 7] = x
	one[a % 7] += 1
	for i in range(len(arr)):
		arr[i] = (arr[i] + one[i]) % (10 ** 9 + 7)
while T:
	T -= 1
	n = int(input())
	A = [int(a) for a in input().split()]
	arr = [0] * 7
	for a in A:
		update(arr, a)
	print(arr[0])


N = int(1000000000.0 + 7)
for a in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	ar = [[0] * 7 for _ in range(n + 1)]
	ar[0][0] = 1
	for i in range(n):
		p = 10 ** len(str(b[i]))
		for j in range(7):
			k = (j * p + b[i]) % 7
			ar[i + 1][j] = (ar[i + 1][j] + ar[i][j]) % N
			ar[i + 1][k] = (ar[i + 1][k] + ar[i][j]) % N
	print((ar[-1][0] - 1 + N) % N)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	arr = []
	for j in range(a + 1):
		arr.append([0] * 7)
	arr[0][0] = 1
	for k in range(a):
		c = 10 ** len(str(b[k]))
		for l in range(7):
			arr[k + 1][l] = (arr[k + 1][l] + arr[k][l]) % 1000000007
			m = (c * l + b[k]) % 7
			arr[k + 1][m] = (arr[k + 1][m] + arr[k][l]) % 1000000007
	arr = arr[::-1]
	print((arr[0][0] - 1 + 1000000007) % 1000000007)


tc = int(input())
for i in range(tc):
	n1 = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for x in range(n1 + 1):
		l1 += [[0] * 7]
	l1[0][0] = 1
	for j in range(n1):
		a = 10 ** len(str(l[j]))
		for k in range(7):
			m = (k * a + l[j]) % 7
			l1[j + 1][k] = (l1[j + 1][k] + l1[j][k]) % (10 ** 9 + 7)
			l1[j + 1][m] = (l1[j + 1][m] + l1[j][k]) % (10 ** 9 + 7)
	l1 = l1[::-1]
	print((l1[0][0] - 1 + (10 ** 9 + 7)) % (10 ** 9 + 7))


import copy
import math
mod = 1000000007
for asdf in range(int(input())):
	length = int(input())
	nums = [int(lol) for lol in input().split()]
	current = [1, 0, 0, 0, 0, 0, 0]
	new = [1, 0, 0, 0, 0, 0, 0]
	currSum = 0
	for i in range(length):
		multi = round(math.pow(10, math.floor(math.log10(nums[i]) + 1)) % 7)
		for j in range(7):
			new[(j * multi + nums[i]) % 7] += current[j]
			new[(j * multi + nums[i]) % 7] %= mod
		current = copy.deepcopy(new)
	print((current[0] - 1) % mod)


K = int(1000000000.0 + 7)
for q in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pp = [[0] * 7 for _ in range(n + 1)]
	pp[0][0] = 1
	for i in range(n):
		p = 10 ** len(str(a[i]))
		for j in range(7):
			k = (j * p + a[i]) % 7
			pp[i + 1][j] = (pp[i + 1][j] + pp[i][j]) % K
			pp[i + 1][k] = (pp[i + 1][k] + pp[i][j]) % K
	print((pp[-1][0] - 1 + K) % K)


A = int(1000000000.0 + 7)
for _ in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	DP = [[0] * 7 for _ in range(N + 1)]
	DP[0][0] = 1
	for i in range(N):
		P = 10 ** len(str(l[i]))
		for j in range(7):
			k = (j * P + l[i]) % 7
			DP[i + 1][j] = (DP[i + 1][j] + DP[i][j]) % A
			DP[i + 1][k] = (DP[i + 1][k] + DP[i][j]) % A
	print((DP[-1][0] - 1 + A) % A)


monu = int(1000000000.0 + 7)
for q in range(int(input())):
	nana = int(input())
	ay = list(map(int, input().split()))
	ap = [[0] * 7 for _ in range(nana + 1)]
	ap[0][0] = 1
	for i in range(nana):
		p = 10 ** len(str(ay[i]))
		for j in range(7):
			k = (j * p + ay[i]) % 7
			ap[i + 1][j] = (ap[i + 1][j] + ap[i][j]) % monu
			ap[i + 1][k] = (ap[i + 1][k] + ap[i][j]) % monu
	print((ap[-1][0] - 1 + monu) % monu)


t = int(input())

def res():
	return 0
for i in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	dynamic_arr = []
	for i in range(n + 1):
		dynamic_arr.append([0] * 7)
	dynamic_arr[0][0] = 1
	for i in range(n):
		length = 10 ** len(str(array[i]))
		for c in range(0, 7, 1):
			z = (c * length + array[i]) % 7
			dynamic_arr[i + 1][c] = (dynamic_arr[i + 1][c] + dynamic_arr[i][c]) % int(1000000000.0 + 7)
			dynamic_arr[i + 1][z] = (dynamic_arr[i + 1][z] + dynamic_arr[i][c]) % int(1000000000.0 + 7)
	print((dynamic_arr[len(dynamic_arr) - 1][0] - 1 + res() + int(1000000000.0 + 7)) % int(1000000000.0 + 7 + res()))


mega = int(1000000000.0 + 7)
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split(' ')))
	dummyArr = [[0] * 7 for _ in range(N + 1)]
	dummyArr[0][0] = 1
	for i in range(N):
		P = 10 ** len(str(arr[i]))
		for j in range(7):
			k = (j * P + arr[i]) % 7
			dummyArr[i + 1][j] = (dummyArr[i + 1][j] + dummyArr[i][j]) % mega
			dummyArr[i + 1][k] = (dummyArr[i + 1][k] + dummyArr[i][j]) % mega
	print((dummyArr[-1][0] - 1 + mega) % mega)


mod = int(1000000007)
for z in range(int(input())):
	mn = int(input())
	arr = list(map(int, input().split()))
	t = [[0] * 7 for _ in range(mn + 1)]
	t[0][0] = 1
	for i in range(mn):
		p = 10 ** len(str(arr[i]))
		for j in range(7):
			k = (j * p + arr[i]) % 7
			t[i + 1][j] = (t[i + 1][j] + t[i][j]) % mod
			t[i + 1][k] = (t[i + 1][k] + t[i][j]) % mod
	print((t[-1][0] - 1 + mod) % mod)


m = int(1000000000.0 + 7)
n = int(input())
while n:
	a = int(input())
	ls = list(map(int, input().split()))[:a]
	b = [[0] * 7 for i in range(0, a + 1)]
	b[0][0] = 1
	for j in range(0, a):
		l = 10 ** len(str(ls[j]))
		for k in range(0, 7):
			p = (k * l + ls[j]) % 7
			b[j + 1][k] = (b[j + 1][k] + b[j][k]) % m
			b[j + 1][p] = (b[j + 1][p] + b[j][k]) % m
	print((b[-1][0] - 1 + m) % m)
	n = n - 1


power = int(1000000000.0 + 7)
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = n + 1
	pp = [[0] * 7 for _ in range(m)]
	pp[0][0] = 1
	for i in range(n):
		d = 10 ** len(str(a[i]))
		for j in range(7):
			k = (j * d + a[i]) % 7
			pp[i + 1][j] = (pp[i + 1][j] + pp[i][j]) % power
			pp[i + 1][k] = (pp[i + 1][k] + pp[i][j]) % power
	print((pp[-1][0] - 1 + power) % power)


x = int(1000000000.0 + 7)
for y in range(int(input())):
	z = int(input())
	a = list(map(int, input().split()))
	b = [[0] * 7 for _ in range(z + 1)]
	b[0][0] = 1
	for i in range(z):
		c = 10 ** len(str(a[i]))
		for j in range(7):
			k = (j * c + a[i]) % 7
			b[i + 1][j] = (b[i + 1][j] + b[i][j]) % x
			b[i + 1][k] = (b[i + 1][k] + b[i][j]) % x
	print((b[-1][0] - 1 + x) % x)


M = int(1000000000.0 + 7)
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	subsets = [[0] * 7 for _ in range(n + 1)]
	subsets[0][0] = 1
	for i in range(n):
		k = 10 ** len(str(a[i]))
		for j in range(7):
			m = (j * k + a[i]) % 7
			subsets[i + 1][j] = (subsets[i + 1][j] + subsets[i][j]) % M
			subsets[i + 1][m] = (subsets[i + 1][m] + subsets[i][j]) % M
	print((subsets[-1][0] - 1 + M) % M)


N = int(1000000000.0 + 7)
for q in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	arr = [[0] * 7 for _ in range(n + 1)]
	arr[0][0] = 1
	for i in range(n):
		s = 10 ** len(str(a[i]))
		for j in range(7):
			k = (j * s + a[i]) % 7
			arr[i + 1][j] = (arr[i + 1][j] + arr[i][j]) % N
			arr[i + 1][k] = (arr[i + 1][k] + arr[i][j]) % N
	print((arr[-1][0] - 1 + N) % N)


kar = int(1000000000.0 + 7)
for govind in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [[0] * 7 for _ in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		p = 10 ** len(str(a[i]))
		for j in range(7):
			k = (j * p + a[i]) % 7
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % kar
			dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % kar
	print((dp[-1][0] - 1 + kar) % kar)


M = int(1000000000.0 + 7)
for k in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [[0] * 7 for _ in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		c = 10 ** len(str(arr[i]))
		for j in range(7):
			k = (j * c + arr[i]) % 7
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % M
			dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % M
	print((dp[-1][0] - 1 + M) % M)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	arr = [[0] * 7 for i in range(n + 1)]
	arr[0][0] = 1
	for i in range(n):
		p = 10 ** len(str(lst[i]))
		for j in range(7):
			x = (j * p + lst[i]) % 7
			arr[i + 1][j] = (arr[i + 1][j] + arr[i][j]) % mod
			arr[i + 1][x] = (arr[i + 1][x] + arr[i][j]) % mod
	print((arr[-1][0] - 1 + mod) % mod)


Mod = int(1000000000.0 + 7)
for q in range(int(input())):
	o = int(input())
	a = list(map(int, input().split()))
	dp = [[0] * 7 for _ in range(o + 1)]
	dp[0][0] = 1
	for d in range(o):
		p = 10 ** len(str(a[d]))
		for g in range(7):
			k = (g * p + a[d]) % 7
			dp[d + 1][g] = (dp[d + 1][g] + dp[d][g]) % Mod
			dp[d + 1][k] = (dp[d + 1][k] + dp[d][g]) % Mod
	print((dp[-1][0] - 1 + Mod) % Mod)


a = int(1000000000.0 + 7)
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	d = [[0] * 7 for _ in range(n + 1)]
	d[0][0] = 1
	for j in range(n):
		p = 10 ** len(str(x[j]))
		for l in range(7):
			w = (l * p + x[j]) % 7
			d[j + 1][l] = (d[j + 1][l] + d[j][l]) % a
			d[j + 1][w] = (d[j + 1][w] + d[j][l]) % a
	print((d[-1][0] - 1 + a) % a)


m = int(1000000000.0 + 7)
test = int(input())
for i in range(test):
	n = int(input())
	l = list(map(int, input().split()))
	dp = [[0] * 7 for j in range(n + 1)]
	dp[0][0] = 1
	for c in range(n):
		q = 10 ** len(str(l[c]))
		for d in range(7):
			k = (d * q + l[c]) % 7
			dp[c + 1][d] = (dp[c + 1][d] + dp[c][d]) % m
			dp[c + 1][k] = (dp[c + 1][k] + dp[c][d]) % m
	print((dp[-1][0] - 1 + m) % m)


M = int(1000000000.0 + 7)
for w in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	wa = [[0] * 7 for i in range(n + 1)]
	wa[0][0] = 1
	for i in range(n):
		p = 10 ** len(str(a[i]))
		for j in range(7):
			k = (j * p + a[i]) % 7
			wa[i + 1][j] = (wa[i + 1][j] + wa[i][j]) % M
			wa[i + 1][k] = (wa[i + 1][k] + wa[i][j]) % M
	print((wa[-1][0] - 1 + M) % M)


temp = int(1000000000.0 + 7)
for q in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = [[0] * 7 for _ in range(n + 1)]
	d[0][0] = 1
	for i in range(n):
		p = 10 ** len(str(arr[i]))
		for j in range(7):
			k = (j * p + arr[i]) % 7
			d[i + 1][j] = (d[i + 1][j] + d[i][j]) % temp
			d[i + 1][k] = (d[i + 1][k] + d[i][j]) % temp
	print((d[-1][0] - 1 + temp) % temp)


mod = int(1000000000.0 + 7)
for a in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	dp = [[0] * 7 for _ in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		q = 10 ** len(str(b[i]))
		for j in range(7):
			k = (j * q + b[i]) % 7
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod
			dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % mod
	print((dp[-1][0] - 1 + mod) % mod)


mod = 10 ** 9 + 7
t = int(input())
for test in range(t):
	n = int(input())
	numbers = [int(x) for x in input().split(' ', n - 1)]
	dp = [[0] * 7 for i in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		power = 10 ** len(str(numbers[i]))
		for j in range(7):
			k = (j * power + numbers[i]) % 7
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod
			dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % mod
	print((dp[-1][0] - 1 + mod) % mod)


Mod = int(1000000000.0 + 7)
for n in range(int(input())):
	length = int(input())
	arr = list(map(int, input().split()))
	dynamic = [[0] * 7 for _ in range(length + 1)]
	dynamic[0][0] = 1
	for qq in range(length):
		pe = 10 ** len(str(arr[qq]))
		for j in range(7):
			data = (arr[qq] + pe * j) % 7
			dynamic[qq + 1][j] = (dynamic[qq + 1][j] + dynamic[qq][j]) % Mod
			dynamic[qq + 1][data] = (dynamic[qq + 1][data] + dynamic[qq][j]) % Mod
	print((dynamic[-1][0] - 1 + Mod) % Mod)


mod = int(1000000000.0 + 7)
for tc in range(int(input())):
	sz = int(input())
	m = list(map(int, input().split()))
	memoize = [[0] * 7 for _ in range(sz + 1)]
	memoize[0][0] = 1
	for x in range(sz):
		v = 10 ** len(str(m[x]))
		for y in range(7):
			z = (y * v + m[x]) % 7
			memoize[x + 1][y] = (memoize[x + 1][y] + memoize[x][y]) % mod
			memoize[x + 1][z] = (memoize[x + 1][z] + memoize[x][y]) % mod
	print((memoize[-1][0] - 1 + mod) % mod)


M = int(1000000000.0 + 7)
for a in range(int(input())):
	b = int(input())
	c = list(map(int, input().split()))
	dp = [[0] * 7 for _ in range(b + 1)]
	dp[0][0] = 1
	for i in range(b):
		p = 10 ** len(str(c[i]))
		for j in range(7):
			k = (j * p + c[i]) % 7
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % M
			dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % M
	print((dp[-1][0] - 1 + M) % M)


m = int(1000000000.0 + 7)
for q in range(int(input())):
	noe = int(input())
	arr = list(map(int, input().split()))
	dp = [[0] * 7 for _ in range(noe + 1)]
	dp[0][0] = 1
	for i in range(noe):
		p = 10 ** len(str(arr[i]))
		for j in range(7):
			k = (j * p + arr[i]) % 7
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % m
			dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % m
	print((dp[-1][0] - 1 + m) % m)


mod = int(1000000000.0 + 7)
for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	qb = [[0] * 7 for _ in range(n + 1)]
	qb[0][0] = 1
	for j in range(n):
		s = 10 ** len(str(p[j]))
		for k in range(7):
			l = (k * s + p[j]) % 7
			qb[j + 1][k] = (qb[j + 1][k] + qb[j][k]) % mod
			qb[j + 1][l] = (qb[j + 1][l] + qb[j][k]) % mod
	print((qb[-1][0] - 1 + mod) % mod)


def Subsequence_Numbers_Divisible_b_7(l, n):
	Di = [[0] * 7 for i in range(n + 2)]
	Di[0][0] = 1
	for i in range(n):
		j = int(len(str(l[i])))
		p = 1
		while j != 0:
			p = p * 10
			j = j - 1
		for k in range(7):
			y = (k * p + l[i]) % 7
			Di[i + 1][k] = (Di[i + 1][k] + Di[i][k]) % 1000000007
			Di[i + 1][y] = (Di[i + 1][y] + Di[i][k]) % 1000000007
	print(int((Di[n][0] - 1 + 1000000007) % 1000000007))
for _ in range(int(input())):
	n = int(input())
	Ai = list(map(int, input().split()))
	Subsequence_Numbers_Divisible_b_7(Ai, n)


M = 1000000007
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = [[0 for i in range(7)] for i in range(n + 1)]
	ans[0][0] = 1
	for i in range(n):
		x = len(str(l[i]))
		p = 1
		for I in range(x):
			p *= 10
		for j in range(7):
			u = (j * p + l[i]) % 7
			ans[i + 1][j] = (ans[i + 1][j] + ans[i][j]) % M
			ans[i + 1][u] = (ans[i + 1][u] + ans[i][j]) % M
	print((ans[n][0] - 1) % M)


x = int(1000000000.0 + 7)
t = int(input())
for i in range(t):
	p = int(input())
	l = list(map(int, input().split()))
	st = [[0] * 7 for x in range(p + 1)]
	st[0][0] = 1
	for j in range(p):
		q = 10 ** len(str(l[j]))
		for k in range(7):
			r = (k * q + l[j]) % 7
			st[j + 1][k] = (st[j + 1][k] + st[j][k]) % x
			st[j + 1][r] = (st[j + 1][r] + st[j][k]) % x
	print((st[-1][0] - 1 + x) % x)


N = int(1000000000.0 + 7)
k = int(input())
for jk in range(k):
	m = int(input())
	lis = list(map(int, input().split()))
	dp = [[0] * 7 for i in range(m + 1)]
	dp[0][0] = 1
	for jp in range(m):
		p = 10 ** len(str(lis[jp]))
		for jl in range(7):
			kp = (jl * p + lis[jp]) % 7
			dp[jp + 1][jl] = (dp[jp + 1][jl] + dp[jp][jl]) % N
			dp[jp + 1][kp] = (dp[jp + 1][kp] + dp[jp][jl]) % N
	print((dp[-1][0] - 1 + N) % N)


val = int(1000000000.0 + 7)
for i in range(int(input())):
	num = int(input())
	p = list(map(int, input().split()))
	dp = [[0] * 7 for _ in range(num + 1)]
	dp[0][0] = 1
	for j in range(num):
		store = 10 ** len(str(p[j]))
		for k in range(7):
			l = (k * store + p[j]) % 7
			dp[j + 1][k] = (dp[j + 1][k] + dp[j][k]) % val
			dp[j + 1][l] = (dp[j + 1][l] + dp[j][k]) % val
	print((dp[-1][0] - 1 + val) % val)


test = int(input())
z = 0
while z < test:
	n = int(input())
	l = list(map(int, input().split()))
	arr = []
	for _ in range(n + 1):
		arr.append([0] * 7)
	arr[0][0] = 1
	i = 0
	M = int(1000000000.0 + 7)
	while i < n:
		p = pow(10, len(str(l[i])))
		j = 0
		while j < 7:
			k = (j * p + l[i]) % 7
			arr[i + 1][k] = (arr[i + 1][k] + arr[i][j]) % M
			arr[i + 1][j] = (arr[i + 1][j] + arr[i][j]) % M
			j += 1
		i += 1
	arr = arr[-1][0]
	res = (arr - 1 + M) % M
	print(res)
	z += 1


for i in range(int(input())):
	x = int(input())
	l = list(map(int, input().split(' ')))
	mod = int(1000000000.0 + 7)
	my = [[0] * 7 for j in range(x + 1)]
	my[0][0] = 1
	for i in range(x):
		p = 10 ** len(str(l[i]))
		for j in range(7):
			k = (j * p + l[i]) % 7
			my[i + 1][j] = (my[i + 1][j] + my[i][j]) % mod
			my[i + 1][k] = (my[i + 1][k] + my[i][j]) % mod
	print((my[-1][0] - 1 + mod) % mod)