We start with a string s consisting only of the digits 1, 2, or 3. The length of s is denoted by |s|. For each i from 1 to |s|, the i-th character of s is denoted by s_i. 

There is one cursor. The cursor's location ℓ is denoted by an integer in \{0, …, |s|\}, with the following meaning: 

  * If ℓ = 0, then the cursor is located before the first character of s. 
  * If ℓ = |s|, then the cursor is located right after the last character of s. 
  * If 0 < ℓ < |s|, then the cursor is located between s_ℓ and s_{ℓ+1}. 



We denote by s_left the string to the left of the cursor and s_right the string to the right of the cursor. 

We also have a string c, which we call our clipboard, which starts out as empty. There are three types of actions:

  * The Move action. Move the cursor one step to the right. This increments ℓ once. 
  * The Cut action. Set c ← s_right, then set s ← s_left. 
  * The Paste action. Append the value of c to the end of the string s. Note that this doesn't modify c. 



The cursor initially starts at ℓ = 0. Then, we perform the following procedure:

  1. Perform the Move action once. 
  2. Perform the Cut action once. 
  3. Perform the Paste action s_ℓ times. 
  4. If ℓ = x, stop. Otherwise, return to step 1. 



You're given the initial string s and the integer x. What is the length of s when the procedure stops? Since this value may be very large, only find it modulo 10^9 + 7. 

It is guaranteed that ℓ ≤ |s| at any time.

Input

The first line of input contains a single integer t (1 ≤ t ≤ 1000) denoting the number of test cases. The next lines contain descriptions of the test cases.

The first line of each test case contains a single integer x (1 ≤ x ≤ 10^6). The second line of each test case consists of the initial string s (1 ≤ |s| ≤ 500). It is guaranteed, that s consists of the characters "1", "2", "3".

It is guaranteed that the sum of x in a single file is at most 10^6. It is guaranteed that in each test case before the procedure will stop it will be true that ℓ ≤ |s| at any time.

Output

For each test case, output a single line containing a single integer denoting the answer for that test case modulo 10^9 + 7. 

Example

Input


4
5
231
7
2323
6
333
24
133321333


Output


25
1438
1101
686531475

Note

Let's illustrate what happens with the first test case. Initially, we have s =  231. Initially, ℓ = 0 and c = \varepsilon (the empty string). The following things happen if we follow the procedure above:

  * Step 1, Move once: we get ℓ = 1. 
  * Step 2, Cut once: we get s =  2 and c =  31. 
  * Step 3, Paste s_ℓ =  2 times: we get s =  23131. 
  * Step 4: ℓ = 1 not= x = 5, so we return to step 1. 

  * Step 1, Move once: we get ℓ = 2. 
  * Step 2, Cut once: we get s =  23 and c =  131. 
  * Step 3, Paste s_ℓ =  3 times: we get s =  23131131131. 
  * Step 4: ℓ = 2 not= x = 5, so we return to step 1. 

  * Step 1, Move once: we get ℓ = 3. 
  * Step 2, Cut once: we get s =  231 and c =  31131131. 
  * Step 3, Paste s_ℓ =  1 time: we get s =  23131131131. 
  * Step 4: ℓ = 3 not= x = 5, so we return to step 1. 

  * Step 1, Move once: we get ℓ = 4. 
  * Step 2, Cut once: we get s =  2313 and c =  1131131. 
  * Step 3, Paste s_ℓ =  3 times: we get s =  2313113113111311311131131. 
  * Step 4: ℓ = 4 not= x = 5, so we return to step 1. 

  * Step 1, Move once: we get ℓ = 5. 
  * Step 2, Cut once: we get s =  23131 and c =  13113111311311131131. 
  * Step 3, Paste s_ℓ =  1 times: we get s =  2313113113111311311131131. 
  * Step 4: ℓ = 5 = x, so we stop. 



At the end of the procedure, s has length 25.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Implementation

Starter code:

Solutions:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
MAX = 10 ** 9 + 7

def solve():
	x = int(input())
	s = [int(i) for i in input()]
	ans = len(s)
	c = ''
	l = 0
	while l < x:
		l += 1
		k = len(s)
		if k < x:
			for i in range(s[l - 1] - 1):
				for j in range(l, k):
					s.append(s[j])
		ans += (s[l - 1] - 1) * (ans - l)
		ans %= MAX
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import math, collections, sys
mod = 10 ** 9 + 7
for _ in range(int(input())):
	x = int(input())
	s = [i for i in input()]
	l = len(s)
	for i in range(1, x + 1):
		rep = int(s[i - 1]) - 1
		if len(s) < x:
			start = i
			end = len(s)
			for j in range(rep):
				for k in range(start, end):
					s.append(s[k])
		l = (l + (l - i) * rep) % mod
	print(l)


import time
import sys
MOD = 1000000000.0 + 7
f = sys.stdin
t1 = time.time()
for t in range(int(f.readline())):
	(x, s) = (int(f.readline().rstrip()), f.readline().rstrip())
	i = 0
	while len(s) < x:
		i += 1
		s += s[i:] * (int(s[i - 1]) - 1)
	answer = len(s)
	while i < x:
		i += 1
		answer = (answer + (answer - i) * (int(s[i - 1]) - 1)) % MOD
	print(int(answer))


for i in range(int(input())):
	x = int(input())
	s = input()
	ans = len(s)
	a = x
	for j in range(1, x + 1):
		if s[j - 1] == '1':
			pass
		elif s[j - 1] == '2':
			ans += ans - j
			ans %= 10 ** 9 + 7
			s = s + s[j:]
		elif s[j - 1] == '3':
			ans += 2 * (ans - j)
			ans %= 10 ** 9 + 7
			s = s + 2 * s[j:]
		if len(s) > x:
			a = j
			break
	for k in range(a + 1, x + 1):
		if s[k - 1] == '1':
			pass
		elif s[k - 1] == '2':
			ans += ans - k
			ans %= 10 ** 9 + 7
		elif s[k - 1] == '3':
			ans += 2 * (ans - k)
			ans %= 10 ** 9 + 7
	ans %= 10 ** 9 + 7
	print(ans)


for _ in range(int(input())):
	x = int(input())
	s = list(map(int, input()))
	ans = len(s)
	l = 1
	while l <= x:
		ans = ((ans - l) * s[l - 1] + l) % 1000000007
		r = len(s)
		for _ in range(s[l - 1] - 1):
			if len(s) < x:
				s += s[l:r]
			else:
				break
		l += 1
	print(ans)


import sys
mod = 10 ** 9 + 7
t = int(sys.stdin.readline())
for _ in range(t):
	x = int(sys.stdin.readline())
	s = [i for i in sys.stdin.readline()][:-1]
	length = len(s)
	for i in range(1, x + 1):
		if len(s) >= x:
			add = (length - i) % mod * ((int(s[i - 1]) - 1) % mod) % mod
			length = (length + add) % mod
		else:
			count = 0
			rep = int(s[i - 1]) - 1
			(start, end) = (i, len(s))
			for k in range(rep):
				for j in range(start, end):
					s.append(s[j])
			add = (length - i) % mod * ((int(s[i - 1]) - 1) % mod) % mod
			length = (length + add) % mod
	print(length)


def solve(s, x):
	n = len(s)
	mod = 10 ** 9 + 7
	for i in range(x):
		n += (n - i - 1) * (int(s[i]) - 1)
		n %= mod
		if len(s) < x:
			s += s[i + 1:] * (int(s[i]) - 1)
	return n
for _ in range(int(input())):
	x = int(input())
	s = input()
	print(solve(s, x))


for _ in range(int(input())):
	x = int(input())
	s = input()
	i = 0
	while len(s) < x:
		s += s[i + 1:] * (int(s[i]) - 1)
		i += 1
	ans = len(s)
	for j in range(i, x):
		ans += (ans - j - 1) * (int(s[j]) - 1)
		ans %= 10 ** 9 + 7
	print(ans)


import sys
import math
from collections import defaultdict, Counter, deque
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = pow(10, 9) + 7
t = int(input())
for i in range(t):
	x = int(input())
	s = list(map(int, input()))
	cur = 0
	tot = len(s) - 1
	while cur < x:
		tot = s[cur] * tot % mod
		if len(s) < x and s[cur] > 1:
			s += s[cur + 1:] * (s[cur] - 1)
		if tot == 0:
			tot = 10 ** 9 + 6
		else:
			tot -= 1
		cur += 1
	ans = (cur + tot + 1) % mod
	print(ans)


import sys
mod = 10 ** 9 + 7
for _ in range(int(input())):
	x = int(input())
	s = list(map(int, input()))
	ans = len(s)
	for i in range(1, x + 1):
		ans = (i + (ans - i) * s[i - 1]) % mod
		r = len(s)
		for _ in range(s[i - 1] - 1):
			if len(s) < x:
				s += s[i:r]
			else:
				break
	print(ans)


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	x = int(input())
	s = input().rstrip('\n')
	X = []
	for (i, si) in enumerate(s):
		if i == x:
			break
		X.append(int(s[i]))
	ans = len(s)
	for i in range(x):
		ans = (ans + (ans - i - 1) * (X[i] - 1)) % mod
		if len(X) < x:
			if X[i] == 1:
				continue
			X_ = X[i + 1:]
			for j in range(X[i] - 1):
				if len(X) < x:
					X.extend(X_)
	print(ans)


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from collections import defaultdict as dd
(t,) = I()
while t:
	t -= 1
	(x,) = I()
	s = list(input())
	n = len(s)
	cur = len(s)
	for i in range(1, x + 1):
		k = int(s[i - 1])
		if k >= 2 and n <= x:
			curn = n
			for j in range(k - 1):
				for ii in range(i, curn):
					s.append(s[ii])
					n += 1
					if n > x:
						break
				if n > x:
					break
		cur = (i + (cur - i) * k % MOD) % MOD
	print(cur % MOD)


import sys
input = sys.stdin.readline
t = int(input())
co = 0
mod = 10 ** 9 + 7
for _ in range(t):
	x = int(input())
	arr = list(map(int, input().strip()))
	note = arr[:]
	ans = len(note)
	for i in range(x):
		ans = (ans - (i + 1)) * note[i] + (i + 1)
		if ans < 0:
			ans += mod
		ans = ans % mod
		temp = []
		for j in range(note[i] - 1):
			if len(note) + len(temp) < x:
				temp += note[i + 1:]
			else:
				break
		note += temp
	print(ans % mod)


n = int(input())
import math

def getdb(s, x):
	l = 1
	length = len(s)
	newS = s + [0] * (3 * x - length)
	while length < x and l <= x:
		i = length - l
		j = length
		for k in range(newS[l - 1] - 1):
			newS[j:j + i] = newS[l:l + i]
			j += i
			length += i
		l += 1
	return newS[0:length]
for i in range(n):
	x = int(input())
	s = [int(x) for x in input()]
	dbli = getdb(s, x)
	tot = len(s)
	l = 1
	while l <= x:
		if tot <= l:
			tot += 10 ** 9 + 7
		tot = l + dbli[l - 1] * (tot - l)
		if math.log(tot) > 9.01:
			tot %= 10 ** 9 + 7
		l += 1
	print(tot % (10 ** 9 + 7))


INF = 10 ** 10

def main():
	print = out.append
	x = get_int()
	P = 10 ** 9 + 7
	li = list(map(int, input()))
	ptr = 0
	res = len(li)
	while ptr < x:
		ptr += 1
		if len(li) < x and li[ptr - 1] > 1:
			li += li[ptr:] * (li[ptr - 1] - 1)
		res -= 1
		res = res * li[ptr - 1] % P
	print((res + ptr) % P)
import sys
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
[main() for _ in range(int(input()))]
print(*out, sep='\n')


from sys import stdin

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))
md = 10 ** 9 + 7

def main():
	t = iin()
	while t:
		t -= 1
		x = iin()
		s = list(input())
		l = len(s)
		ans = l
		i = 0
		while i < x:
			i += 1
			ch = int(s[i - 1])
			ans = (i + ch * (ans - i)) % md
			if l >= x:
				continue
			incr = l
			ss = []
			for _ in range(ch):
				for j in range(i, l):
					if incr < ans and incr < x:
						ss.append(s[j])
						incr += 1
					else:
						break
			l = incr
			for k in ss:
				s.append(k)
		print(ans % md)
main()


import sys, math
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	x = int(input())
	s = list(map(int, list(input())))
	ans = len(s)
	(l, lens) = (1, len(s))
	s = s + [0] * (x - len(s))
	for l in range(1, x + 1):
		for i in range(lens, min((lens - l) * s[l - 1] + l, len(s))):
			s[i] = s[l + i - lens]
		lens = min((lens - l) * s[l - 1] + l, len(s))
		if lens == len(s):
			break
	for l in range(1, x + 1):
		ans = ((ans - l) * s[l - 1] + l) % MOD
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	x = int(input())
	s = [k for k in input()]
	ls = len(s)
	(cur, length) = (1, len(s))
	curr = cur
	twothree = s.count('2') + s.count('3')
	while cur != len(s) and len(s) < x + 69:
		while len(s) == length + (length - cur) * (int(s[cur - 1]) - 1):
			if not twothree or cur == len(s):
				break
			if int(s[cur - 1]) > 1:
				twothree -= 1
			cur += 1
			length = len(s)
			curr = cur
		if not twothree or cur == len(s):
			break
		s += [s[curr]]
		if int(s[curr]) > 1:
			twothree += 1
		curr += 1
		if curr == length:
			curr = cur
	ans = ls
	mod = 10 ** 9 + 7
	for i in range(x):
		try:
			ans = (ans + (int(s[i]) - 1) * (ans - i - 1)) % mod
		except:
			break
	print(ans)


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
import random
from queue import PriorityQueue
from collections import Counter as cc
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop
from itertools import permutations
from math import factorial as f

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
import sys
t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	x = int(input())
	s = list(input())
	i = 0
	ans = len(s)
	while i < x:
		j = i + 1
		z = int(s[i]) - 1
		k = 0
		ha = len(s)
		if len(s) < x:
			while k != z:
				s.append(s[j])
				if j == ha - 1:
					k += 1
					j = i + 1
				else:
					j += 1
			ans = len(s)
		else:
			z1 = ans - j
			ans = ans + z1 * z
			ans %= mod
		i += 1
	print(ans % mod)


import sys
reader = (line.rstrip() for line in sys.stdin)
t = int(next(reader))
modulo = 10 ** 9 + 7
for _ in range(t):
	x = int(next(reader))
	s = [int(i) for i in next(reader)]
	l = 0
	total = len(s)
	while l < x:
		l += 1
		k = s[l - 1]
		if len(s) < x:
			n = len(s)
			for _ in range(k - 1):
				s.extend(s[l:n])
			total = len(s)
		else:
			total += (k - 1) * (total - l)
			total %= modulo
	print(total)


n = int(input())
mod = 10 ** 9 + 7
for j in range(n):
	x = int(input())
	sleft = str(input())
	length = len(sleft)
	l = 0
	while len(sleft) < x:
		l += 1
		if sleft[l - 1] == '2':
			sright = sleft[l:]
			sleft += sright
		elif sleft[l - 1] == '3':
			sright = sleft[l:]
			sleft += sright * 2
		else:
			continue
	for l in range(1, x + 1):
		mult = int(sleft[l - 1])
		length = l + mult * ((length - l) % mod)
		length = length % mod
	print(length)


def main():
	TT = int(input())
	for _ in range(TT):
		x = int(input())
		s = [int(c) for c in input().strip()]
		ans = len(s)
		for l in range(0, x):
			ans += (ans - l - 1) * (s[l] - 1)
			ans %= 1000000007
			end = len(s)
			for _ in range(1, s[l]):
				if len(s) > x + 1:
					break
				for c in range(l + 1, end):
					if len(s) > x + 1:
						break
					s.append(s[c])
		print(ans)
main()


for _ in range(int(input())):
	x = int(input())
	s = list(input())
	l = 0
	ans = len(s)
	while l < x:
		if ans >= x:
			break
		temp = len(s)
		ans += (int(s[l]) - 1) * (temp - l - 1)
		for i in range(int(s[l]) - 1):
			if len(s) > x:
				break
			for j in range(l + 1, temp):
				s.append(s[j])
				if len(s) > x:
					break
		l += 1
	while l < x:
		temp = ans
		ans += (int(s[l]) - 1) * (temp - l - 1)
		ans = ans % (10 ** 9 + 7)
		l += 1
	print(ans)


t = int(input())
for i in range(t):
	x = int(input())
	y = input()
	s = []
	for j in y:
		s.append(j)
	l = 0
	res = len(s)
	while l != x:
		if len(s) < x:
			le = len(s)
			for p in range(int(s[l]) - 1):
				for j in range(l + 1, le):
					s.append(s[j])
		res = (res + (res - l - 1) * (int(s[l]) - 1)) % (10 ** 9 + 7)
		l += 1
	print(res % (10 ** 9 + 7))


MOD = 10 ** 9 + 7

def main():
	x = int(input())
	s = input()
	ln = len(s)
	key = 0
	for l in range(x):
		num = int(s[l]) - 1
		if num == 0:
			continue
		if ln < x and (not key):
			s += s[l + 1:] * num
		r = (ln - l - 1) * num
		ln += r
		if ln >= MOD:
			key = 1
		ln %= MOD
	print(ln % MOD)
t = int(input())
for _ in range(t):
	main()


ttt = int(input())
mod = 10 ** 9 + 7
s = '#' * (10 ** 6 + 1500)
s = list(s)
for bo in range(ttt):
	x = int(input())
	st = input()
	s[1:len(st) + 1] = list(st)
	siz = len(st)
	p = 0
	while siz < x:
		p += 1
		whe = siz
		for de4d in range(int(s[p]) - 1):
			for k in range(p + 1, whe + 1):
				siz += 1
				s[siz] = s[k]
				if siz > x:
					break
			if siz > x:
				break
		if siz > x:
			break
	ans = len(st)
	for i in range(1, x + 1):
		ans = i + (ans - i) * int(s[i])
		ans = ans % mod
	print(ans)


M = 1000000007
t = int(input())
while t:
	t += -1
	x = int(input())
	s = input()
	i = 0
	while len(s) < x:
		s += s[i + 1:] * (int(s[i]) - 1)
		i += 1
	n = len(s)
	for j in range(i, x):
		tmp = n - (j + 1)
		n = j + 1 + tmp * int(s[j])
		n = n % M
	print(n % M)


t = int(input())
ans = []
arr = [None] * 10 ** 6
cur = 0
MOD = 10 ** 9 + 7
for _ in range(t):
	(x, s) = (int(input()), list(map(int, str(input()))))
	max_p = cur + x
	for i in range(cur, min(max_p, cur + len(s))):
		arr[i] = s[i - cur]

	def copy(start, length, times):
		b = start + length
		for i in range(times):
			for j in range(length):
				if b >= max_p:
					return
				arr[b] = arr[start + j]
				b += 1
	val = len(s)
	cnt = 1
	while x:
		if arr[max_p - 1] is None and arr[cur] > 1:
			copy(cur + 1, val - cnt, arr[cur] - 1)
		val = (cnt + (val - cnt) * arr[cur]) % MOD
		cnt += 1
		cur += 1
		x -= 1
	ans.append(val)
for a in ans:
	print(a)


from sys import stdin
from sys import stdout
mod = 1000000007
for i in range(int(stdin.readline())):
	x = int(stdin.readline())
	s = input()
	ans = len(s)
	l = 1
	if len(s) < x:
		while l <= x:
			c = s[l:]
			if s[l - 1] == '2':
				s = s + c
				if len(s) >= x:
					break
			elif s[l - 1] == '3':
				s = s + c
				if len(s) >= x:
					break
				s = s + c
				if len(s) >= x:
					break
			l += 1
	l = 1
	while l <= x:
		cc = ans - l
		if s[l - 1] == '2':
			ans = (ans + cc) % mod
		elif s[l - 1] == '3':
			ans = (ans + cc) % mod
			ans = (ans + cc) % mod
		l += 1
	stdout.write(str(ans) + '\n')
	stdout.flush()


for _ in range(int(input())):
	n = int(input())
	a = [0] * n
	tmp = input()
	ans = last = len(tmp)
	for (i, x) in enumerate(tmp):
		if i == n:
			last = n
			break
		a[i] = int(x)
	for i in range(n):
		ans = (ans - i - 1) * a[i] + i + 1
		ans %= 10 ** 9 + 7
		k = last
		for _ in range(a[i] - 1):
			for j in range(i + 1, last):
				if k == n:
					break
				a[k] = a[j]
				k += 1
		last = k
	print(ans % (10 ** 9 + 7))


M = int(1000000000.0 + 7)
n = int(input())
while n > 0:
	n -= 1
	x = int(input())
	s = input()
	idx = 0
	length = len(s)
	while length < x:
		t = ord(s[idx]) - ord('1')
		s += s[idx + 1:] * t
		length += (length - idx - 1) * t
		idx += 1
	while idx != x:
		t = ord(s[idx]) - ord('1')
		length += (length - idx - 1) * t % M
		idx += 1
	print(length % M)


import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	x = int(input())
	s = list(map(int, list(input())))
	ans = len(s)
	cnt = ans
	flg = True
	for i in range(x):
		ans += (s[i] - 1) * (ans - i - 1)
		if len(s) > x:
			flg = False
		if flg:
			l = len(s)
			for j in range((l - i - 1) * (s[i] - 1)):
				s.append(s[i + 1 + j % (l - i - 1)])
				cnt += 1
				if cnt > x:
					break
		ans %= mod
	print(ans)


import sys
import bisect
import heapq
from math import *
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
mod = pow(10, 9) + 7

def inp():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def graph(vertex):
	return [[] for i in range(0, vertex + 1)]

def zerolist(n):
	return [0] * n

def nl():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def solve():
	x = int(inp())
	a = list(inp())
	for i in range(0, len(a)):
		a[i] = int(a[i])
	ans = len(a)
	p = 0
	f = True
	while ans < x:
		for j in range(a[p] - 1):
			for i in range(p + 1, int(ans)):
				a.append(a[i])
		ans += (a[p] - 1) * ((ans - p - 1 + mod) % mod)
		p += 1
	for j in range(p, x):
		ans += (a[j] - 1) * ((ans - j - 1 + mod) % mod)
		ans %= mod
	print(int(ans % mod))
testcase(int(inp()))


import sys
T = int(sys.stdin.readline().strip())
for _ in range(T):
	x = int(sys.stdin.readline().strip())
	s = list(sys.stdin.readline().strip())
	ls = len(s)
	for l in range(x):
		t = ord(s[l]) - ord('0') - 1
		ls = (ls + (ls - l - 1) * t) % (10 ** 9 + 7)
		e = len(s)
		while len(s) <= x and t > 0:
			s += s[l + 1:e]
			t -= 1
	print(ls)


def main():
	MOD = int(1000000000.0 + 7)
	n = int(input())
	string = str(input())
	i = 0
	while len(string) < n:
		temp = int(string[i])
		string = string + string[i + 1:] * (temp - 1)
		i += 1
	ans = len(string)
	if i < n:
		while i < n:
			temp = int(string[i])
			ans += (temp - 1) * (ans - i - 1)
			ans = ans % MOD
			i += 1
	print(ans)
	return

def test():
	t = int(input())
	while t:
		main()
		t -= 1
	return
test()


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
mod = 10 ** 9 + 7

def solve():
	x = int(input())
	s = [int(i) for i in input()]
	ans = len(s)
	cur = -1
	while cur != x - 1:
		cur += 1
		if len(s) < x:
			k = len(s)
			for _ in range(s[cur] - 1):
				for j in range(cur + 1, k):
					s.append(s[j])
		ans += (s[cur] - 1) * (ans - (cur + 1))
		ans %= mod
	print(ans)
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	x = int(input())
	a = input()
	l = len(a)
	a = [i for i in a]
	ans = l
	p = 0
	m = 10 ** 9 + 7
	while ans < x:
		for j in range(int(a[p]) - 1):
			for i in range(p + 1, ans):
				a.append(a[i])
		ans += (int(a[p]) - 1) * ((ans - p - 1 + m) % m)
		p += 1
	for j in range(p, x):
		ans += (int(a[j]) - 1) * ((ans - j - 1 + m) % m)
		ans %= m
	print(ans)


import sys, os.path
import math
from collections import defaultdict, deque
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
S = lambda : list(map(str, input()))

def main():
	(t,) = I()
	for t1 in range(t):
		(x,) = I()
		s2 = str(input()).rstrip('\n')
		s1 = []
		for i in range(len(s2)):
			if i > x:
				break
			s1.append(int(s2[i]))
		count1 = len(s2)
		count1 %= 10 ** 9 + 7
		for i in range(x):
			k = int(s1[i])
			count1 -= 1
			count1 %= 10 ** 9 + 7
			if len(s1) > x:
				count1 *= k
				count1 %= 10 ** 9 + 7
			else:
				if k == 1:
					continue
				X = s1[i + 1:]
				l1 = len(s1)
				for j in range(k - 1):
					if len(s1) < x:
						s1.extend(X)
				count1 *= k
				count1 %= 10 ** 9 + 7
		count1 += x
		count1 %= 10 ** 9 + 7
		print(count1)
main()