Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:512 MB

#114. Duplicate Strings

统计

题目描述

给出仅包含小写字母的字符串字符串 $s$,$q$ 次操作,第 $i$ 次操作把当前的 $s$ 复制 $k$ 次后接在自己后面,或求字符串中字符 $c$ 的出现次数,对 $10^9+7$ 取模。

输入格式

第一行两个正整数 $n,q$,$n$ 表示字符串长度。$(1\le n,q\le 10^5)$

接下来一行一个字符串 $s$,仅包含小写字母。

接下来 $q$ 行,每行第一个正整数 $op$ 表示操作类型。$(1\le op\le 2)$

  • $op=1$,则后接一个整数 $k$,表示把当前的 $s$ 复制 $k$ 次后接在自己后面。$(0\le k\le 10^9)$
  • $op=2$,则后接一个小写字母 $c$,表示求 $s$ 中 $c$ 的出现次数。

输出格式

对每个询问操作输出答案。

输入输出样例

样例输入

3 3
aba
1 5
2 a
2 b

样例输出

12
6

样例解释

第一次操作后,字符串变为 abaabaabaabaabaaba