← 返回题目列表

Codeforces · 666/C

C. 码字

中文机器翻译题面 查看原题

著名雕塑家西加索是雷伯兰间谍!

这是今天 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。