Assimilate

半角英字で構成された長さ$N$の文字列$S$が与えられます。 これから、クエリが$Q$個与えられます。

クエリ番号が$1$の時には、任意の位置に半角英字$c$で構成された長さ$K$の文字列を挿入します。

クエリ番号が$2$の時は、現在の文字列の取り得る形の種類の数をmod$1000000007$で出力してください。

制約

• $1\leq N \leq 10^5$
• $|S|=N$
• $1\leq Q \leq 1000$
• $q \in \{1, 2\}$
• $1 \leq K \leq 300$

入力形式

N S
Q
q_1 c_1 K_1
...
q_Q c_Q K_Q