著名雕塑家西加索是雷伯兰间谍!
这是今天 Berlandian 报纸上的重大新闻。现在雕塑家躲了起来。这次你把庇护所交给了大师。您有一个受保护的掩体,并将其提供给您的朋友。你设置的安全系统只有你才能打开地堡。打开它应该解决对别人来说很难但对你来说很简单的问题。
地堡每天都会生成一个代码字 s。每当有人想要进入掩体时,屏幕上就会出现整数n。作为答案,应该输入另一个整数——长度为 n 的字符串数量模 109 + 7 的余数,该字符串仅由小写英文字母组成,并且包含字符串 s 作为子序列。
字符串 a 的子序列是字符串 b,可以通过从字符串 a 中删除一些符号(可以不删除或全部删除)来从字符串 a 派生出字符串 b。特别是任何字符串都是其自身的子序列。例如,字符串“cfo”是字符串“codeforces”的子序列。
您尚未实现计算正确答案的算法,您应该尽快执行。
输入
第一行包含整数 m (1 ≤ m ≤ 105) — 测试用例中的事件数。
第二行包含非空字符串 s — 沙坑当天生成的字符串。
接下来的 m 行包含事件的描述。描述从整数 t 开始——事件的类型。
如果 t = 1,则认为新的一天已经到来,现在使用新的字符串 s。在这种情况下,同一行包含字符串 s 的新值。
如果 t = 2,则给出整数 n (1 ≤ n ≤ 105)。该事件意味着需要找到当前字符串 s 和值 n 的答案。
所有生成的字符串的长度总和不超过105。所有给定的字符串仅由小写英文字母组成。
输出
对于类型 2 的每个查询,在单独的行上打印模 109 + 7 的答案。
示例
输入 #1
3 a 2 2 1 bc 2 5
输出 #1
51 162626
注意
在第一个事件单词中,形式为“a?”和“?a”都被计算在内,哪里?是任意符号。每种类型都有 26 个单词,但单词“aa”满足两种模式,因此答案是 51。