题目描述

给出仅包含小写字母的字符串字符串 $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。