CF666C.Codeword

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.

著名雕塑家西卡索是一名雷贝尔兰间谍！

今天，这则消息登上了贝尔兰各大报纸的头版头条。如今，这位雕塑家正在躲藏。这一次，你为大师提供了庇护所。你拥有一处受保护的地堡，并将其提供给了你的朋友。你将安全系统设置为仅你本人可以打开地堡。要打开它，必须解决一道对他人而言困难、但对你而言简单的题目。

每天，地堡会生成一个密码词 $s$。每当有人试图进入地堡时，屏幕上会显示一个整数 $n$。作为答案，需输入另一个整数——即：长度为 $n$、仅由小写英文字母构成、且以字符串 $s$ 作为子序列的字符串个数，对 $10^9 + 7$ 取模后的余数。

字符串 $a$ 的子序列是指：通过从 $a$ 中删除若干字符（可能不删，也可能全部删除）后得到的字符串 $b$。特别地，任意字符串都是其自身的子序列。例如，字符串 "cfo" 是 "codeforces" 的一个子序列。

你尚未实现用于计算正确答案的算法，因此必须尽快完成该算法的编写。

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.

第一行包含一个整数 $m$（$1 \leq m \leq 10^5$）—— 表示该测试用例中事件的数量。

第二行包含一个非空字符串 $s$ —— 表示避难所为当天生成的字符串。

接下来的 $m$ 行描述了各个事件。每行事件描述以一个整数 $t$ 开头 —— 表示事件类型。

若 $t = 1$，表示新的一天到来，此时将启用一个新的字符串 $s$；该行随后还包含这个新字符串 $s$ 的值。

若 $t = 2$，则给出一个整数 $n$（$1 \leq n \leq 10^5$）。该事件表示需要针对当前字符串 $s$ 和给定值 $n$ 计算答案。

所有生成字符串的长度总和不超过 $10^5$。所有给定字符串均由小写英文字母组成。

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

对于每个类型为 2 的查询，在单独一行输出答案对 $10^9 + 7$ 取模的结果。

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.

在第一个事件中，统计形如 “a?” 和 “?a” 的单词，其中 ? 表示任意一个字母。这两类单词各有 26 个，但单词 “aa” 同时满足两种模式，因此答案为 51。