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 $\ell$ is denoted by an integer in $\{0, \ldots, |s|\}$, with the following meaning:   If $\ell = 0$, then the cursor is located before the first character of $s$.  If $\ell = |s|$, then the cursor is located right after the last character of $s$.  If $0 < \ell < |s|$, then the cursor is located between $s_\ell$ and $s_{\ell+1}$. 

We denote by $s_\text{left}$ the string to the left of the cursor and $s_\text{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 $\ell$ once.  The Cut action. Set $c \leftarrow s_\text{right}$, then set $s \leftarrow s_\text{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 $\ell = 0$. Then, we perform the following procedure:  Perform the Move action once.  Perform the Cut action once.  Perform the Paste action $s_\ell$ times.  If $\ell = 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 $\ell \le |s|$ at any time.


-----Input-----

The first line of input contains a single integer $t$ ($1 \le t \le 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 \le x \le 10^6$). The second line of each test case consists of the initial string $s$ ($1 \le |s| \le 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 $\ell \le |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, $\ell = 0$ and $c = \varepsilon$ (the empty string). The following things happen if we follow the procedure above:

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

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

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

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

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

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

Difficulty: competition

Starter code:

Solutions:
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 = list(input())
    n = len(s) - 1
    for i in range(n):
        s[i] = int(s[i])

    memo = {}
    for i in range(n):
        memo[i] = s[i]

    ans = len(memo)
    pos = i + 1
    for i in range(x):
        tmp = pos
        if tmp <= x:
            for j in range(memo[i]-1):
                for k in range(i+1, pos):
                    memo[tmp] = memo[k]
                    tmp += 1
            pos = tmp
            ans = tmp
        else:
            ans = ans + (ans - i-1) * (memo[i] - 1)
            ans %= MOD
    print(ans%MOD)

t=int(input())
for _ in range(t):
    mod=1000000007
    x=int(input())
    r=input()
    n=len(r)
    s=[]
    for i in range(n):
        s.append(r[i])    
    f=True
    for i in range(1,x+1):
        o=ord(s[i-1])-ord('0')
        if(f):
            for j in range(1,o):
                for k in range(i,n):
                    s.append(s[k])
            n=len(s)
        else:
            if(o==2):
                n+=(n-i)
                n%=mod
            elif(o==3):
                n+=(2*(n-i))
                n%=mod
        if(n>x and f):
            f=False
    print(n)


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)

from collections import defaultdict as dc
'''from collections import deque as dq
from bisect import bisect_left,bisect_right,insort_left'''
import sys
import math
#define of c++ as inl=input()
mod=10**9 +7
def bs(a,x):
    i=bisect_left(a,x)
    if i!=len(a):
        return i
    else:
        return len(a)
def bs(a,b):
    l=a
    r=b+1
    x=b
    ans=0
    while(l<r):
        mid=(l+r)//2
        if x|mid>ans:
            ans=x|mid
            l=mid+1
        else:
            r=mid
    return ans
def digit(n):
    a=[]
    while(n>0):
        a.append(n%10)
        n=n//10
    return a
def inp():
    p=int(input())
    return p
def line():
    p=list(map(int,input().split()))
    return p
def ans(a,p,z,t):
    q=[]
    for i in range(len(a)):
        if p[a[i]]==t and z>0 and p[a[i][::-1]]==0:
            q.append(i+1)
            z=z-1
    return q
            
for i in range(inp()):
    x=inp()
    s=str(input())
    n=len(s)
    p=n
    for i in range(1,x+1):
        if s[i-1]!='1':
            p=(p%mod+((p-i)%mod * (int(s[i-1])-1)%mod)%mod)%mod
            if len(s)<x:
                z=s[i:]
                s=s+z*(int(s[i-1])-1)
    print(p)

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)