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 {
	
	static InputReader in = new InputReader(System.in);
	static PrintWriter out = new PrintWriter(System.out);
	
	static int oo = (int)1e9;
//	static long oo = (long)1e15;
	static int mod = 1_000_000_007;
	
	static int[] di = {1, 0, 0, -1};
	static int[] dj = {0, -1, 1, 0};
	
	static int M = 40;
	static double EPS = 1e-13;
	
	
	public static void main(String[] args) throws IOException {

		int t = in.nextInt();
		while(t --> 0) {
			int x = in.nextInt();
			char[] ca = in.readString().toCharArray();
			ArrayList<Integer> a = new ArrayList<Integer>();
			for(char c : ca)
				a.add(c - '0');
			int len = a.size();
			for(int i = 1; i <= x; ++i) {
//				int c = a.get(i-1);
//				int r = (len - i + mod) % mod;
//				int b = a.size();
//				for(int j = 1; j < c; ++j) {
//					for(int k = i; k < b && a.size() < x + 5; ++k) {
//						a.add(a.get(k));
//					}
//					len = (len + r) % mod;
//				}

				int c = a.get(i-1);
				int r = (len - i + mod) % mod;
				int b = a.size();
				ArrayList<Integer> add = new ArrayList<Integer>();
				for(int j = 1; j < c; ++j) {
					for(int k = i; k < b && a.size() + add.size() < x + 5; ++k) {
						add.add(a.get(k));
					}
				}
				a.addAll(add);
				for(int j = 1; j < c; ++j) {
					len = (len + r) % mod;
				}
			}
			out.println(len);
		}
		
		out.close();
	}
	
	static int find(int[] g, int x) {
		return g[x] = g[x] == x ? x : find(g, g[x]);
	}
	
	static void union(int[] g, int[] size, int x, int y) {
		x = find(g, x); y = find(g, y);
		if(x == y)
			return;
		if(size[x] < size[y]) {
			g[x] = y;
			size[y] += size[x];
		}
		else {
			g[y] = x;
			size[x] += size[y];
		}
	}
	
	static class Segment {
		Segment left, right;
		int size, val;
		int time, lazy;
		
		public Segment(int[] a, int l, int r) {
			super();
			if(l == r) {
				return;
			}
			int mid = (l + r) / 2;
			left = new Segment(a, l, mid);
			right = new Segment(a, mid+1, r);
		}
		
		boolean covered(int ll, int rr, int l, int r) {
			return ll <= l && rr >= r;
		}
		
		boolean noIntersection(int ll, int rr, int l, int r) {
			return ll > r || rr < l;
		}
		
		void lazyPropagation() {
			if(lazy != 0) {
				if(left != null) {
					left.setLazy(this.time, this.lazy);
					right.setLazy(this.time, this.lazy);
				}
				else {
					val = lazy;
				}
			}
		}
		
		void setLazy(int time, int lazy) {
			if(this.time != 0 && this.time <= time)
				return;
			this.time = time;
			this.lazy = lazy;
		}
		
		int query(int ll, int rr, int l, int r) {
			lazyPropagation();
			if(noIntersection(ll, rr, l, r))
				return 0;
			if(covered(ll, rr, l, r))
				return val;
			int mid = (l + r) / 2;
			int leftSum = left.query(ll, rr, l, mid);
			int rightSum = right.query(ll, rr, mid+1, r);
			return leftSum + rightSum;
		}
		
		int query(int k, int l, int r) {
			Segment trace = this;
			while(l < r) {
				int mid = (l + r) / 2;
				if(trace.left.size > k) {
					trace = trace.left;
					r = mid;
				}
				else {
					k -= trace.left.size;
					trace = trace.right;
					l = mid + 1;
				}
			}
			return l;
		}
		
		void update(int ll, int rr, int time, int knight, int l, int r) {
			lazyPropagation();
			if(noIntersection(ll, rr, l, r))
				return;
			if(covered(ll, rr, l, r)) {
				setLazy(time, knight);
				return;
			}
			int mid = (l + r) / 2;
			left.update(ll, rr, time, knight, l, mid);
			right.update(ll, rr, time, knight, mid+1, r);
		}
	}
	
	static long pow(long a, long n, long mod) {
		if(n == 0)
			return 1;
		if(n % 2 == 1)
			return a * pow(a, n-1, mod) % mod;
		long x = pow(a, n / 2, mod);
		return x * x % mod;
	}
	
	
	static int[] getPi(char[] a) {
		int m = a.length;
		int j = 0;
		int[] pi = new int[m];
		for(int i = 1; i < m; ++i) {
			while(j > 0 && a[i] != a[j])
				j = pi[j-1];
			if(a[i] == a[j]) {
				pi[i] = j + 1;
				j++;
			}
		}
		return pi;
	}
	
	static long lcm(long a, long b) {
		return a * b / gcd(a, b);
	}
	
	static boolean nextPermutation(int[] a) {
		for(int i = a.length - 2; i >= 0; --i) {
			if(a[i] < a[i+1]) {
				for(int j = a.length - 1; ; --j) {
					if(a[i] < a[j]) {
						int t = a[i];
						a[i] = a[j];
						a[j] = t;
						for(i++, j = a.length - 1; i < j; ++i, --j) {
							t = a[i];
							a[i] = a[j];
							a[j] = t;
						}
						return true;
					}
				}
			}
		}
		return false;
	}
	
	static void shuffle(Object[] a) {
		Random r = new Random();
		for(int i = a.length - 1; i > 0; --i) {
			int si = r.nextInt(i);
			Object t = a[si];
			a[si] = a[i];
			a[i] = t;
		}
	}
	
	static void shuffle(int[] a) {
		Random r = new Random();
		for(int i = a.length - 1; i > 0; --i) {
			int si = r.nextInt(i);
			int t = a[si];
			a[si] = a[i];
			a[i] = t;
		}
	}
	
	static void shuffle(long[] a) {
		Random r = new Random();
		for(int i = a.length - 1; i > 0; --i) {
			int si = r.nextInt(i);
			long t = a[si];
			a[si] = a[i];
			a[i] = t;
		}
	}
	
	static int lower_bound(int[] a, int n, int k) {
		int s = 0;
		int e = n;
		int m;
		while (e - s > 0) {
			m = (s + e) / 2;
			if (a[m] < k)
				s = m + 1;
			else
				e = m;
		}
		return e;
	}
	static int lower_bound(long[] a, int n, long k) {
		int s = 0;
		int e = n;
		int m;
		while (e - s > 0) {
			m = (s + e) / 2;
			if (a[m] < k)
				s = m + 1;
			else
				e = m;
		}
		return e;
	}
	
	static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	
	static class Pair implements Comparable<Pair> {
		int first, second;
 
		public Pair(int first, int second) {
			super();
			this.first = first;
			this.second = second;
		}
 
		@Override
		public int compareTo(Pair o) {
			return this.first != o.first ? this.first - o.first : this.second - o.second;
		}
		
//		@Override
//		public int compareTo(Pair o) {
//			return this.first != o.first ? o.first - this.first : o.second - this.second;
//		}
 
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + first;
			result = prime * result + second;
			return result;
		}
 
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;
			if (first != other.first)
				return false;
			if (second != other.second)
				return false;
			return true;
		}
	}
}
 
 
 
class InputReader {
 
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;
 
	public InputReader(InputStream st) {
		this.stream = st;
	}
 
	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}
 
	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
 
	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
 
	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}
 
	public String readString() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}
 
	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}
 
	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
 
	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
 
}