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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/** Class: Codewords.java
 *  @author
 *  @version 1.0 <p>
 *  Course:
 *  Written / Updated: Jun 18, 2016
 *
 *  Purpose - VALID
 */
public class Codewords2 {

	/* As stated in the pdf, we're supposed to print each answer modulo 10^9 + 7. */
	private static final long MODULO = (long)Math.pow(10, 9) + 7;
	/* The pdf says that n will never exceed 10^5. Since our index will begin at 1, we'll allocate 100001 space. */
	private static final int N = 100001;
	/* If the string length exceeds the below cutoff, we'll compute the answer using a different method, for efficiency. */
	private static final int CUTOFF = (int)Math.sqrt(N);
	/* Array of factorials % MODULO, for easy computation of combinatorics % MODULO. */
	private long[] factorial;
	/* Array of modular inverses % MODULO. Useful for computation of combinatorics % MODULO.
	 * See Codewords - Modular inverses and Codewords - MOdular multiplicative inverses.pdf. */
	private long[] inv;
	/* 25^0, 25^1, ...25^N, for computing our answer. */
	private long[] powerOf25;
	/* 26^0 thru 26^N, for computing our answer. */
	private long[] powerOf26;
	/* Array of answers for specific values of the string length that exceed the CUTOFF. */
	private long[] ans;

	public Codewords2() {
		/* Initialize all the arrays */
		this.factorial = new long[N];
		this.factorial[0] = 1;	//0! = 1.
		this.inv = new long[N];
		this.inv[0] = 1;
		this.powerOf25 = new long[N];
		this.powerOf26 = new long[N];
		this.powerOf25[0] = 1; //25^0 = 1
		this.powerOf26[0] = 1; //26^0 = 1

		/* Compute all the arrays up to N */
		for (int i = 1; i < N; ++i) {
			this.factorial[i] = (factorial[i-1] * i) % MODULO;
			/*  See Codewords - Modular inverses and Codewords - MOdular multiplicative inverses.pdf
			 * for how we compute inv[i] below. */
			this.inv[i] = powMod(factorial[i], MODULO - 2);
			this.powerOf25[i] = (25 * this.powerOf25[i-1]) % MODULO;
			this.powerOf26[i] = (26 * this.powerOf26[i-1]) % MODULO;
		}

		this.ans = new long[N];

		try {
			BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));

            //Read the first line
            String line = rd.readLine();
            StringTokenizer tokenizer = new StringTokenizer(line);

            /* The number of the events in the test case. */
            int m = Integer.parseInt(tokenizer.nextToken());

            //Read second line - a nonempty string s.
            String s = rd.readLine();
            if (s.length() > CUTOFF) {
            	prepare(s.length());
            }

            /* 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 <= 10^5). 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 10^5. All of the given strings consist only of lowercase English letters. */
            for (int i = 0; i < m; i++) {
            	line = rd.readLine();
            	tokenizer = new StringTokenizer(line);
            	if (Integer.parseInt(tokenizer.nextToken()) == 1) {
            		s = tokenizer.nextToken();
            		if (s.length() > CUTOFF) {
            			/* See my long comment under count() method to help understand what the below prepare() method does.
            			 * It basically prepares the answers for the above given string length and ALL values of n from 0 thru N,
            			 * where n = the number of blanks. */
            			prepare(s.length());
            		} else {
            			//do nothing
            		}
            	} else {
            		int n = Integer.parseInt(tokenizer.nextToken());
            		count(n, s);	//custom method
            	}
            }

            rd.close();
		} catch (IOException ioe) {
			ioe.printStackTrace();
		}
	}
	//end public Codewords

	/**
	 * Method: prepare
	 * @param sl the String length
	 */
	private void prepare(int sl) {
		long base = 1;
		/* n = number of blanks. We're trying to compute
		 * the number of possible strings of length n that contains a subsequence of the given string
		 * whose length is sl. */
		for (int n = 0; n < N; ++n) {
			if (n >= sl) {
				ans[n] = (this.C(n - 1, sl - 1) * base) % MODULO;
				base = base * 25 % MODULO;
			/* If n < sl, then no. of blanks are less than the string length.
			 * There is no possible string of this many blanks that contain a subsequence of this string.*/
			} else {
				ans[n] = 0;
			}
		}
		for (int n = 0; n < N; ++n) {
			if (ans[n] >= MODULO) {
				ans[n] -= MODULO;
			}
			if (n + 1 < N) {
				ans[n + 1] += (ans[n] * 26) % MODULO;
			}
		}
	}

	/**
	 * Method: powMod
	 * @param a
	 * @param b
	 * @return a^b % MODULO
	 */
	public long powMod(long a, long b) {
		/* To see how this works efficiently, it's worth debugging this
		 * with some small examples and stepping thru each line of code. */
		long ret = 1;
		while (b > 0) {
			if (b % 2 == 1) {
				ret = ret * a % MODULO;
			}
			a = (a * a) % MODULO;
			b >>= 1;		//equivalent to b /= 2;
		}
		return ret;
	}

	/**
	 * Method: count
	 * @param n no. of blanks
	 * @param s the given String
	 * Prints out the possible total no. of strings of length n that contains s as a subsequence.
	 */
	private void count(int n, String s) {
		/* Base case: if the string length is the same as the no. of blanks,
		 * there is only 1 possible such string. */
		if (s.length() == n) {
			System.out.println("1");
			return;
		}
		/* Let's say s == "ab" and n = 3. Then the question is,
		 * how many possible 3-letter strings exist that contain the subSEQUENCE (not substring) "ab"?
		 * Let's count the no. of possible positions of "a" and "b":
		 *
		 * ab_
		 * a_b
		 * _ab
		 *
		 * In sum, there are a total of C(3,2) = 3 possible positions of "a" and "b".
		 * Now, how many possible alphabet characters can go into the remaining 2 blanks in each case?
		 * Naively, we'd think that, since there are 26 alphabets, the answer would be 26 in each of the 3 cases.
		 * So we'd think the answer is 26+26+26 = 78.
		 *
		 * BUT! this results in some duplicates. For example: abb could appear multiple times, because they would be
		 * possible in each of the following cases:
		 * ab_
		 * a_b
		 *
		 * So we need to ensure that we do not double- or triple-count any duplicate strings. How can we ensure this?
		 * Consider:
		 * 1) At any point after "b", we can use any of the 26 characters we want.
		 * 2) At any point between "a" and "b" we can use any of 25 characters.
		 * 3) At any point before "a", we can use any of 25 characters.
		 *
		 * So, the answer for the above case is:
		 * ab__ : 26^2
		 * a_b_ : 25*26
		 * a__b : 25^2
		 * _ab_ : 25*26
		 * _a_b : 25^2
		 * __ab : 25^2
		 *
		 * You will see that the above strategy always works. You can test it out with a simple case:
		 *
		 * Let n = 4 and s = "ab", and the VALID CHARACTERS ARE ONLY "a" and "b". Then:
		 * ab__
		 * a_b_
		 * a__b
		 * _ab_
		 * _a_b
		 * __ab
		 *
		 * There are total of C(4,2) = 6 possible arrangements of the subsequence "a" and "b".
		 * Now, the possible no. of strings are as follows:
		 * ab__ : abaa, abab, abba, abbb
		 * a_b_ : aaba, aabb, abba, abbb
		 * a__b : aaab, aabb, abab, abbb
		 * _ab_ : aaba, aabb, baba, babb
		 * _a_b : aaab, aabb, baab, babb
		 * __ab : aaab, abab, baab, bbab
		 *
		 * Discounting all the duplicates above, we have the following number of unique strings:
		 * abaa, abab, abba, abbb, aaba, aabb, aaab, baba, babb, baab, bbab
		 * That's a total of 11 unique strings.
		 *
		 * The above result comports with our strategy:
		 *
		 * ab__ : 2 blanks at the end, 2 valid characters: 	2*2 = 4
		 * a_b_ : 2 blanks, one appears before "b" :		1*2 = 2
		 * a__b : 2 blanks, both appear before "b" :		1*1 = 1
		 * _ab_ : 2 blanks, one appears before "b" : 		1*2 = 2
		 * _a_b : 2 blanks, both appear before "b" : 		1*1 = 1
		 * __ab : 2 blanks, both appear before "b" : 		1*1 = 1
		 *
		 * So that's a total of 4+2+1+2+1+1 = 11 unique strings.
		 *
		 * The above strategy can be generalized of course, for arbitrary n and arbitrary s.
		 * In fact, note that it doesn't matter what specific characters the String s consists of. The same strategy holds.
		 *
		 * The above strategy can be generalized to the following formula:
		 *
		 * Summation_{n}{k = |s|} C(k-1, |s| - 1) * (q-1)^(k-|s|) * q^(n-k)
		 *
		 * where q = the number of VALID characters.
		 *
		 * For example, when n = 4 and |s| = 2 and q = 2
		 * (e.g. s = "ab" and n = 4-character string, and q consists of "a" and "b" as in the above example we solved):
		 * Applying the above formula:
		 *
		 *   C(1,1) * (2-1)^(2-1) * 2^(4-2) + C(2,1) * (2-1)^(3-1) * 2^(4-3) + C(3,1) * (2-1)^(4-1) * 2^(4-4)
		 * = 1      *    1 ^ 1    * 2^2     + 2      *    1 ^ 2    * 2^1     + 3      *     1^ 3    * 2^0
		 * =                          4     +                        4       +                        3
		 * = 11
		 *
		 * which is exactly the same answer we got above.
		 *
		 * Now, read Codewords - Properties of Modular addition and Codewords - Properties of Modular multiplication.pdf,
		 * (we're supposed to output each of our answers % MODULO).
		 *
		 * */

		/* If string length exceeds cutoff, just print the answer saved in the array and return */
		if (s.length() > CUTOFF) {
			System.out.println(this.ans[n]);
			return;
		}

		/* Else, if no. of blanks is less than string length, the answer is 0. Return. */
		if (n < s.length()) {
			System.out.println("0");
			return;
		}

		/* Else, go ahead and compute the answer. Note that this method is faster than the (now commented out) method below,
		 * because the for loop goes from s.length() - 1 down to 0. And since this string length cannot be longer than
		 * the CUTOFF (otherwise, the above if statement would've triggered and we'd never get to this point in the code),
		 * the for loop only runs a total of CUTOFF times.
		 * I'll leave it to you as an exercise to show that the below loop in fact gets us the same answer as the original strategy
		 * which I outlined in my long comment above and which is implemented further below in the (commented-out) code. */
		long ans = powMod(26, n);
		long base = powMod(25, n - s.length() + 1);
		for (int i = s.length() - 1; i >= 0; --i) {
			ans -= (long)C(n, i) * base % MODULO;
			if (ans < 0) {
				ans += MODULO;
			}
			base = (long)base * 25 % MODULO;
		}
		System.out.println(ans);
		return;

//		long answer = 0;
//		for (int k = s.length(); k <= n; k++) {
//			answer += (((this.C(k-1, s.length() - 1) * this.powerOf25[k - s.length()]) % MODULO) * this.powerOf26[n-k]) % MODULO;
//		}
//		System.out.println(answer % MODULO);
	}

	/**
	 * Method: C
	 * @param k
	 * @param s
	 * @return (k choose s) % MODULO
	 */
	public long C(int k, int s) {
		/* (k choose s) % MODULO
		 * = k!/(s!*(k-s)! % MODULO
		 * = [k! * invOfFactorial(s) * invOfFactorial(k-s)] % MODULO
		 * = ((k! * invOfFactorial(s)) % MODULO * invOfFactorial(k-s)) % MODULO */
		return (((this.factorial[k] * this.inv[s]) % MODULO) * this.inv[k-s]) % MODULO;
	}

	public static void main(String[] args) {
		new Codewords2();
//		System.out.println(cw.C(100, 41));
//		System.out.println(cw.powMod(3, 5));

		/* Testing out combination method */
//		System.out.println(cw.C(10,3));	//120
//		System.out.println(cw.C(11,5));	//462
//		System.out.println(cw.C(11,6));	//462
//		System.out.println(cw.C(46,44));	//1035
//		System.out.println(cw.C(5,3));	//10
//		System.out.println(cw.C(100,41));//2.011644021 * 10^28
	}

}