Problem: The famous sculptor Cicasso is a Reberlandian spy!

These is breaking news in Berlandian papers today. And now the sculptor is hiding. This time you give the shelter to the maestro. You have a protected bunker and you provide it to your friend. You set the security system in such way that only you can open the bunker. To open it one should solve the problem which is hard for others but is simple for you.

Every day the bunker generates a codeword s. Every time someone wants to enter the bunker, integer n appears on the screen. As the answer one should enter another integer — the residue modulo 109 + 7 of the number of strings of length n that consist only of lowercase English letters and contain the string s as the subsequence.

The subsequence of string a is a string b that can be derived from the string a by removing some symbols from it (maybe none or all of them). In particular any string is the subsequence of itself. For example, the string "cfo" is the subsequence of the string "codeforces".

You haven't implemented the algorithm that calculates the correct answers yet and you should do that ASAP.

Input

The first line contains integer m (1 ≤ m ≤ 105) — the number of the events in the test case.

The second line contains nonempty string s — the string generated by the bunker for the current day.

The next m lines contain the description of the events. The description starts from integer t — the type of the event.

If t = 1 consider a new day has come and now a new string s is used. In that case the same line contains a new value of the string s.

If t = 2 integer n is given (1 ≤ n ≤ 105). This event means that it's needed to find the answer for the current string s and the value n.

The sum of lengths of all generated strings doesn't exceed 105. All of the given strings consist only of lowercase English letters.

Output

For each query of the type 2 print the answer modulo 109 + 7 on the separate line.

Example

Input

3
a
2 2
1 bc
2 5


Output

51
162626

Note

In the first event words of the form "a?" and "?a" are counted, where ? is an arbitrary symbol. There are 26 words of each of these types, but the word "aa" satisfies both patterns, so the answer is 51.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, mod = 1e9 + 7;
namespace fft {
struct num {
  double x, y;
  num() { x = y = 0; }
  num(double x, double y) : x(x), y(y) {}
};
inline num operator+(num a, num b) { return num(a.x + b.x, a.y + b.y); }
inline num operator-(num a, num b) { return num(a.x - b.x, a.y - b.y); }
inline num operator*(num a, num b) {
  return num(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline num conj(num a) { return num(a.x, -a.y); }
int base = 1;
vector<num> roots = {{0, 0}, {1, 0}};
vector<int> rev = {0, 1};
const double PI = acosl(-1.0);
void ensure_base(int nbase) {
  if (nbase <= base) return;
  rev.resize(1 << nbase);
  for (int i = 0; i < (1 << nbase); i++)
    rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
  roots.resize(1 << nbase);
  while (base < nbase) {
    double angle = 2 * PI / (1 << (base + 1));
    for (int i = 1 << (base - 1); i < (1 << base); i++) {
      roots[i << 1] = roots[i];
      double angle_i = angle * (2 * i + 1 - (1 << base));
      roots[(i << 1) + 1] = num(cos(angle_i), sin(angle_i));
    }
    base++;
  }
}
void fft(vector<num> &a, int n = -1) {
  if (n == -1) n = a.size();
  assert((n & (n - 1)) == 0);
  int zeros = __builtin_ctz(n);
  ensure_base(zeros);
  int shift = base - zeros;
  for (int i = 0; i < n; i++)
    if (i < (rev[i] >> shift)) swap(a[i], a[rev[i] >> shift]);
  for (int k = 1; k < n; k <<= 1) {
    for (int i = 0; i < n; i += 2 * k) {
      for (int j = 0; j < k; j++) {
        num z = a[i + j + k] * roots[j + k];
        a[i + j + k] = a[i + j] - z;
        a[i + j] = a[i + j] + z;
      }
    }
  }
}
vector<num> fa, fb;
vector<int> multiply(vector<int> &a, vector<int> &b) {
  int need = a.size() + b.size() - 1;
  int nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  int sz = 1 << nbase;
  if (sz > (int)fa.size()) fa.resize(sz);
  for (int i = 0; i < sz; i++) {
    int x = (i < (int)a.size() ? a[i] : 0);
    int y = (i < (int)b.size() ? b[i] : 0);
    fa[i] = num(x, y);
  }
  fft(fa, sz);
  num r(0, -0.25 / sz);
  for (int i = 0; i <= (sz >> 1); i++) {
    int j = (sz - i) & (sz - 1);
    num z = (fa[j] * fa[j] - conj(fa[i] * fa[i])) * r;
    if (i != j) fa[j] = (fa[i] * fa[i] - conj(fa[j] * fa[j])) * r;
    fa[i] = z;
  }
  fft(fa, sz);
  vector<int> res(need);
  for (int i = 0; i < need; i++) res[i] = fa[i].x + 0.5;
  return res;
}
vector<int> multiply_mod(vector<int> &a, vector<int> &b, int m, int eq = 0) {
  int need = a.size() + b.size() - 1;
  int nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  int sz = 1 << nbase;
  if (sz > (int)fa.size()) fa.resize(sz);
  for (int i = 0; i < (int)a.size(); i++) {
    int x = (a[i] % m + m) % m;
    fa[i] = num(x & ((1 << 15) - 1), x >> 15);
  }
  fill(fa.begin() + a.size(), fa.begin() + sz, num{0, 0});
  fft(fa, sz);
  if (sz > (int)fb.size()) fb.resize(sz);
  if (eq)
    copy(fa.begin(), fa.begin() + sz, fb.begin());
  else {
    for (int i = 0; i < (int)b.size(); i++) {
      int x = (b[i] % m + m) % m;
      fb[i] = num(x & ((1 << 15) - 1), x >> 15);
    }
    fill(fb.begin() + b.size(), fb.begin() + sz, num{0, 0});
    fft(fb, sz);
  }
  double ratio = 0.25 / sz;
  num r2(0, -1), r3(ratio, 0), r4(0, -ratio), r5(0, 1);
  for (int i = 0; i <= (sz >> 1); i++) {
    int j = (sz - i) & (sz - 1);
    num a1 = (fa[i] + conj(fa[j]));
    num a2 = (fa[i] - conj(fa[j])) * r2;
    num b1 = (fb[i] + conj(fb[j])) * r3;
    num b2 = (fb[i] - conj(fb[j])) * r4;
    if (i != j) {
      num c1 = (fa[j] + conj(fa[i]));
      num c2 = (fa[j] - conj(fa[i])) * r2;
      num d1 = (fb[j] + conj(fb[i])) * r3;
      num d2 = (fb[j] - conj(fb[i])) * r4;
      fa[i] = c1 * d1 + c2 * d2 * r5;
      fb[i] = c1 * d2 + c2 * d1;
    }
    fa[j] = a1 * b1 + a2 * b2 * r5;
    fb[j] = a1 * b2 + a2 * b1;
  }
  fft(fa, sz);
  fft(fb, sz);
  vector<int> res(need);
  for (int i = 0; i < need; i++) {
    long long aa = fa[i].x + 0.5;
    long long bb = fb[i].x + 0.5;
    long long cc = fa[i].y + 0.5;
    res[i] = (aa + ((bb % m) << 15) + ((cc % m) << 30)) % m;
  }
  return res;
}
vector<int> square_mod(vector<int> &a, int m) {
  return multiply_mod(a, a, m, 1);
}
};  // namespace fft
int m, len, n[N];
char s[N];
vector<int> p[N];
long long pw(long long x, long long p) {
  if (!p) return 1;
  long long z = pw(x, p / 2);
  z *= z;
  z %= mod;
  if (p % 2 == 0) return z;
  z *= x;
  z %= mod;
  return z;
}
long long fac[N];
long long faci[N];
vector<int> b;
vector<int> build(int len) {
  vector<int> a;
  for (int i = 0; i < len; i++) {
    a.push_back(faci[i]);
  }
  return fft::multiply_mod(a, b, mod);
}
long long res[N];
long long pw1[N];
int main() {
  fac[0] = 1;
  faci[0] = 1;
  for (int i = 1; i < N; i++) {
    fac[i] = fac[i - 1] * i;
    fac[i] %= mod;
    faci[i] = pw(fac[i], mod - 2);
  }
  long long z;
  pw1[0] = 1;
  for (int i = 0; i < N; i++) {
    z = pw1[i] * faci[i];
    z %= mod;
    b.push_back(z);
    pw1[i + 1] = pw1[i] * 25;
    pw1[i + 1] %= mod;
  }
  cin >> m;
  scanf("%s", s);
  len = strlen(s);
  int t;
  map<int, int> st;
  int num = 0;
  st[len] = num++;
  for (int i = 0; i < m; i++) {
    scanf("%d", &t);
    n[i] = -1;
    if (t == 1) {
      scanf("%s", s);
      len = strlen(s);
      if (st.count(len)) continue;
      st[len] = num++;
    } else {
      scanf("%d", &n[i]);
      p[st[len]].push_back(i);
    }
  }
  int sq = 1000;
  long long r, all, n1;
  for (map<int, int>::iterator it = st.begin(); it != st.end(); it++) {
    len = it->first;
    if (it->first > sq) {
      vector<int> ml = build(it->first);
      for (int i = 0; i < p[it->second].size(); i++) {
        int in = p[it->second][i];
        if (n[in] < len) {
          res[in] = 0;
          continue;
        }
        r = fac[n[in]] * ml[n[in]];
        r %= mod;
        all = pw(26, n[in]);
        all -= r;
        all %= mod;
        all += mod;
        all %= mod;
        res[in] = all;
      }
    } else {
      len = it->first;
      for (int i = 0; i < p[it->second].size(); i++) {
        int in = p[it->second][i];
        n1 = n[in];
        if (n[in] < len) {
          res[in] = 0;
          continue;
        }
        for (int j = 0; j < len; j++) {
          r = pw1[n1 - j] * faci[j];
          r %= mod;
          r *= faci[n1 - j];
          r %= mod;
          res[in] += r;
          if (res[in] >= mod) res[in] -= mod;
        }
        res[in] *= fac[n1];
        res[in] %= mod;
        all = pw(26, n[in]);
        all -= res[in];
        all %= mod;
        all += mod;
        all %= mod;
        res[in] = all;
      }
    }
  }
  for (int i = 0; i < m; i++) {
    if (n[i] == -1) continue;
    printf("%lld\n", res[i]);
  }
  return 0;
}