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. 
import java.io.*;
import java.math.BigInteger;
import java.util.*;

// written by luchy0120

public class Main {
    public static void main(String[] args) throws Exception {

        new Main().run();
    }


    int color[],dfn[],low[],stack[],cnt[];
    boolean vis[];
    boolean iscut[];
    int deep,top,n,m,sum,ans;
    List<Integer> g[];

    void tarjan(int u,int fa)
    {
        int child = 0;
        dfn[u]=++deep;
        low[u]=deep;
        vis[u]=true;
        stack[++top]=u;
        int sz=g[u].size();
        for(int i=0;i<sz;i++)
        {
            int v =g[u].get(i);
            if(v==fa) continue;
            if(dfn[v]==0)
            {
                child++;
                tarjan(v,u);
                low[u]=Math.min(low[u],low[v]);

            }
            else
            {
                if(vis[v])
                {
                    low[u]=Math.min(low[u],low[v]);
                }
            }
        }
        if(fa<0&&child==1){
            iscut[u] =true;
        }

        if(dfn[u]==low[u])
        {
            iscut[u] = true;
            color[u]=++sum;
            vis[u]=false;
            while(stack[top]!=u)
            {
                color[stack[top]]=sum;
                vis[stack[top--]]=false;
            }
            top--;
        }
    }
    boolean hasV  = false;
    boolean hasU  = false;
    long ct = 0;
    void dfs(int u,int fa,int a,int b){
        ct++;
        vis[u] = true;
        int sz=g[u].size();
        for(int i=0;i<sz;i++) {
            int v = g[u].get(i);
            if (v == fa) continue;
            if(vis[v]) continue;
            if(v==a){
                hasV = true;
                continue;
            }
            if(v==b){
                hasU = true;
                continue;
            }
            dfs(v,u,a,b);


        }
    }

//    void solve() {
//
//    }




//    int get_room(int i,int j){
//        return i/3*3 + j/3;
//    }

//    int a[][] = new int[9][9];
//    int space = 0;
//
//    boolean vis_row[][] = new boolean[9][10];
//    boolean vis_col[][] = new boolean[9][10];
//    boolean vis_room[][] = new boolean[9][10];
//    int val[][][] =new int[9][9][];
//    int prepare[][];
//
//    void dfs(int rt){
//
//    }

    void solve(){
        int t =ni();

        long mod = 1000000007;
        ot:for(int i=0;i<t;++i){
            int x =ni();
            String s = ns();
            StringBuilder sb = new StringBuilder(s);
            long len = s.length();
            int p = 0;
            int g = 0;

            while(p!=x){

                p++;
                long right = len-p;
                right = (right%mod + mod)%mod;

                int d = sb.charAt(p-1)-'0';


                if(d==1){


                }else if(d==2){
                    len += right;
                    int l = sb.length();
                    if(l<x) {
                        for (int f = p; f < l; ++f) {
                            sb.append(sb.charAt(f));
                        }
                    }


                }else{
                    len += right*2L;
                    int l = sb.length();
                    if(l<x) {
                        for (int f = p; f < l; ++f) {
                            sb.append(sb.charAt(f));
                        }
                        for (int f = p; f < l; ++f) {
                            sb.append(sb.charAt(f));
                        }
                    }
                }
                len = (len)%mod;



            }

            println(len);



        }


    }


//    int gt(char v){
//        if(v=='('){
//            return 4;
//        }else if(v=='+'||v=='-'){
//            return 1;
//        }else if(v=='8'){
//            return 2;
//        }
//        return 3;
//    }
//
//        void solve() {
//            String s = ns();
//            int n = ni();
//            // '(' 4  '+' 1  '-' 1  '*' 2  '^' 3
//
//            long mod = 100007;
//            ot:
//            for (int i = 0; i < n; ++i) {
//                char[] p = ns().toCharArray();
//                int len = p.length;
//                int op = 0;
//                for (int j = 0; j < len; ++j) {
//                    if (p[j] == '(') {
//                        op++;
//                    } else if (p[j] == ')') {
//                        op--;
//                    }
//                    if (op < 0) {
//                        continue ot;
//                    }
//                }
//
//                for(long val = 1;val<=1000;++val) {
//                    char stop[] = new char[len];
//                    int p1 = 0;
//                    long stnum[] = new long[len];
//                    int p2 = 0;
//                    long cur = 0;
//                    for (int j = 0; j < len; ) {
//                        if (p[j] == '(') {
//                            stop[p1++] = p[j];
//                            j++;
//                        } else if (p[j] == ')') {
//                            j++;
//                            while(stop[p1-1]!='('){
//                                p1--;
//                                char c = stop[p1];
//                                long op1 = stnum[--p2];
//                                long op2 = stnum[--p2];
//                                if (c == '+') {
//                                    stnum[p2++] = (op1 + op2) % mod;
//                                } else if (c == '-') {
//                                    stnum[p2++] = (op2 - op1) % mod;
//                                } else if (c == '*') {
//                                    stnum[p2++] = (op2 * op1) % mod;
//                                } else if (c == '^') {
//                                    stnum[p2++] = mod_pow(op2, op1, mod);
//                                }
//                            }
//                            p1--;
//                        } else if (p[j] >= '0' && p[j] <= '9') {
//                            while (j < len && p[j] >= '0' && p[j] <= '9') {
//                                cur = cur * 10 + (p[j] - '0');
//                                j++;
//                            }
//                            stnum[p2++] = cur;
//                            cur = 0;
//                        } else if (p[j] == 'a') {
//                            stnum[p2++] = val;
//                        } else {
//                            int me = gt(p[j]);
//                            if (p1 > 0 && gt(stop[p1 - 1]) >= me) {
//                                p1--;
//                                char c = stop[p1];
//                                long op1 = stnum[--p2];
//                                long op2 = stnum[--p2];
//                                if (c == '+') {
//                                    stnum[p2++] = (op1 + op2) % mod;
//                                } else if (c == '-') {
//                                    stnum[p2++] = (op2 - op1) % mod;
//                                } else if (c == '*') {
//                                    stnum[p2++] = (op2 * op1) % mod;
//                                } else if (c == '^') {
//                                    stnum[p2++] = mod_pow(op2, op1, mod);
//                                }
//                            }
//                            stop[p1++] = p[j];
//                        }
//                    }
//                    while (p1 > 0) {
//                        p1--;
//                        char c = stop[p1];
//                        long op1 = stnum[--p2];
//                        long op2 = stnum[--p2];
//                        if (c == '+') {
//                            stnum[p2++] = (op1 + op2) % mod;
//                        } else if (c == '-') {
//                            stnum[p2++] = (op2 - op1) % mod;
//                        } else if (c == '*') {
//                            stnum[p2++] = (op2 * op1) % mod;
//                        } else if (c == '^') {
//                            stnum[p2++] = mod_pow(op2, op1, mod);
//                        }
//                    }
//                    long res= stnum[0];
//                }
//
//
//            }
//        }
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//    }




    static long mul(long a, long b, long p)
    {
        long res=0,base=a;
        while(b>0)
        {
            if((b&1L)>0)
                res=(res+base)%p;
            base=(base+base)%p;
            b>>=1;
        }
        return res;
    }


    static long mod_pow(long k,long n,long p){
        long res = 1L;
        long temp = k%p;
        while(n!=0L){
            if((n&1L)==1L){
                res = mul(res,temp,p);
            }
            temp = mul(temp,temp,p);
            n = n>>1L;
        }
        return res%p;
    }
    public static String roundS(double result, int scale){
        String fmt = String.format("%%.%df", scale);
        return String.format(fmt, result);
    }








//    void solve() {
//
//        for(int i=0;i<9;++i) {
//            for (int j = 0; j < 9; ++j) {
//                int v = ni();
//                a[i][j] = v;
//                if(v>0) {
//                    vis_row[i][v] = true;
//                    vis_col[j][v] = true;
//                    vis_room[get_room(i, j)][v] = true;
//                }else{
//                    space++;
//                }
//            }
//        }
//
//
//        prepare = new int[space][2];
//
//        int p = 0;
//
//        for(int i=0;i<9;++i) {
//            for (int j = 0; j < 9; ++j) {
//                if(a[i][j]==0){
//                    prepare[p][0] = i;
//                    prepare[p][1]= j;p++;
//                    List<Integer> temp =new ArrayList<>();
//                    for(int k=1;k<=9;++k){
//                        if(!vis_col[j][k]&&!vis_row[i][k]&&!vis_room[get_room(i,j)][k]){
//                            temp.add(k);
//                        }
//                    }
//                    int sz = temp.size();
//                    val[i][j] = new int[sz];
//                    for(int k=0;k<sz;++k){
//                        val[i][j][k] = temp.get(k);
//                    }
//                }
//            }
//        }
//        Arrays.sort(prepare,(x,y)->{
//           return Integer.compare(val[x[0]][x[1]].length,val[y[0]][y[1]].length);
//        });
//        dfs(0);
//
//
//
//
//
//
//
//
//
//
//    }




    InputStream is;
    PrintWriter out;

    void run() throws Exception {
        is = System.in;
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private char ncc() {
        int b = readByte();
        return (char) b;
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private String nline() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[][] nm(int n, int m) {
        char[][] a = new char[n][];
        for (int i = 0; i < n; i++) a[i] = ns(m);
        return a;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private long[] nal(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nl();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) {
        }
        ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) {
        }
        ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();
        }
    }

    void print(Object obj) {
        out.print(obj);
    }

    void println(Object obj) {
        out.println(obj);
    }

    void println() {
        out.println();
    }

    void printArray(int a[],int from){
        int l = a.length;
        for(int i=from;i<l;++i){
            print(a[i]);
            if(i!=l-1){
                print(" ");
            }
        }
        println();
    }

    void printArray(long a[],int from){
        int l = a.length;
        for(int i=from;i<l;++i){
            print(a[i]);
            if(i!=l-1){
                print(" ");
            }
        }
        println();
    }
}