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. 
#include <bits/stdc++.h>
using namespace std;
bool sortbysec(const pair<pair<long long, long long>, long long> &a,
               const pair<pair<long long, long long>, long long> &b) {
  return (a.second < b.second);
}
string add(string st1, string st2) {
  long long r = 0;
  string ans;
  ans.resize(3000);
  for (long long i = 2999; i >= 0; i--) {
    long long x = st1[i] - '0';
    long long y = st2[i] - '0';
    long long z = x + y + r;
    if (z >= 10) {
      r = 1;
    } else
      r = 0;
    ans[i] = (z % 10) + '0';
  }
  return ans;
}
long long p(long long x) { return ((x % 1000000007) * 2) % 1000000007; }
long long mat[1005][1005];
long long f(long long h, set<long long> s, long long ans) {
  if (h <= 1) {
    return ans;
  }
  cout << ans << endl;
  long long ans1, ans2, ans3, ans4;
  if (s.find(h - 1) == s.end()) {
    ans1 = f(h - 1, s, ans);
  } else {
    ans1 = f(h - 1, s, ans + 1);
  }
  if (s.find(h - 1) == s.end()) {
    ans2 = f(h - 2, s, ans + 1);
  } else {
    ans2 = f(h - 2, s, ans);
  }
  cout << ans1 << " " << ans2 << "t\n";
  return min(ans1, ans2);
}
long long ar[100000 + 5];
long long prevs[1000];
long long cnt[1000];
double f(double x) { return ((pow(4, x)) + pow(6, x) - pow(9, x)); }
long long gcd(long long a, long long b);
long long power(long long x, unsigned long long y, unsigned long long m);
long long modInverse(long long a, long long m) {
  long long g = gcd(a, m);
  if (g != 1)
    ;
  else {
    return power(a, m - 2, m);
  }
}
long long power(long long x, unsigned long long y, unsigned long long m) {
  if (y == 0) return 1;
  long long p = power(x, y / 2, m) % m;
  p = (p * p) % m;
  return (y % 2 == 0) ? p : (x * p) % m;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
int main() {
  long long q;
  cin >> q;
  while (q--) {
    long long x;
    string st;
    cin >> x;
    cin >> st;
    if (st.size() == 1) {
      cout << 1 << endl;
      continue;
    }
    string st1 = st;
    long long i = 0;
    long long a = st[0] - '0';
    while (st.size() <= x) {
      long long s = st.size();
      for (long long j = 0; j < a - 1; j++) {
        for (long long k = i + 1; k < s; k++) {
          st.push_back(st[k]);
        }
      }
      i++;
      if (st.size() >= x) break;
      a = st[i] - '0';
    }
    i = 0;
    long long l = 1;
    a = st[0] - '0';
    long long sz = st1.size();
    long long m = 1000000000 + 7;
    for (long long i = 0; i < x;) {
      long long l = i + 1;
      sz = (((sz - l + m) % m * a % m) % m + l % m) % m;
      i++;
      if (i == x) break;
      a = (st[i] - '0') % m;
    }
    cout << sz % m << endl;
  }
}
