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.util.*;

public class Main {
    public static final boolean DO_LOG = false; // TODO: move to run params
    private static Logger log = new Logger();

    static class Task {

        static final int MOD = 1_000_000_000 + 7;

        PrintWriter out;
        MyScanner in;

        public void solve(MyScanner in, PrintWriter out) {
            this.in = in;
            this.out = out;

            if (false) {
                Random random = new Random();
                log.info("100");
                for (int i = 0; i < 100; i++) {
                    log.info("" + Math.abs(random.nextInt(10_0000)));
                    int l = random.nextInt(500);
                    StringBuilder sb = new StringBuilder();
                    for (int k = 0; k < l; k++) {
                        sb.append(1 + random.nextInt(3));
                    }
                    log.info(sb.toString());
                }
                System.exit(0);

            }
            // *_*
            int t = in.nextInt();
            for (int asdas = 0; asdas < t; asdas++) {
                int x = in.nextInt();
                int first[] =  new int[x + 1];
                int first_pointer = 0;
                String s = in.nextLine();
                for (int i = 0; i < s.length(); i++) {
                    if (first.length > i + 1) {
                        first[i + 1] = s.charAt(i) - '0';
                    }
                }
                long l = 0, r = s.length();
                first_pointer = (int) r;
                int turn = 0;
                while (true) {
                    // move
                    l++; r--;
                    if (r < 0) r += MOD;


                    // paste sL times... what is sL (1, 2, 3)
                    int sl = first[(int)l]; // ?

                    for (int pt =1; pt < sl && first_pointer < x; pt++) {
                        for (int i = (int) l + 1; first_pointer < x && i < l + 1 + r; i++) {
                            first_pointer++;
                            first[first_pointer] = first[i];
                        }
                    }
                    r = (sl * r) % MOD;

                    if (l == x) {
                        break;
                    }
                }

                out.println((l + r) % MOD);
            }

        }

    }

    public static void main(String[] args) {

        MyScanner in = new MyScanner();
        PrintWriter out = new PrintWriter(System.out);
        Task solver = new Task();

        solver.solve(in, out);

        out.close();
    }

    public static class Logger {

        public void info(String s) {
            if (DO_LOG) {
                System.out.println(s);
            }
        }
    }

    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

/*me after this round
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░▄▄███▄▄▄░▄▄██▄░░░░░░░
░░░░░░░░░██▀███████████████▀▀▄█░░░░░░
░░░░░░░░█▀▄▀▀▄██████████████▄░░█░░░░░
░░░░░░░█▀▀░▄██████████████▄█▀░░▀▄░░░░
░░░░░▄▀░░░▀▀▄████████████████▄░░░█░░░
░░░░░▀░░░░▄███▀░░███▄████░████░░░░▀▄░
░░░▄▀░░░░▄████░░▀▀░▀░░░░░░██░▀▄░░░░▀▄
░▄▀░░░░░▄▀▀██▀░░░░░▄░░▀▄░░██░░░▀▄░░░░
█░░░░░█▀░░░██▄░░░░░▀▀█▀░░░█░░░░░░█░░░
█░░░▄▀░░░░░░██░░░░░▀██▀░░█▀▄░░░░░░▀▀▀
▀▀▀▀░▄▄▄▄▄▄▀▀░█░░░░░░░░░▄█░░█▀▀▀▀▀█░░
░░░░█░░░▀▀░░░░░░▀▄░░░▄▄██░░░█░░░░░▀▄░
░░░░█░░░░░░░░░░░░█▄▀▀▀▀▀█░░░█░░░░░░█░
░░░░▀░░░░░░░░░░░░░▀░░░░▀░░░░▀░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
 */