問題文

英小文字からなる長さNの文字列が M 個与えられ、 S_1, S_2, ..., S_M とします。以下のクエリを Q 個処理して下さい。

• swapクエリ(type = 1, x, y, l, r): S_x[l..r] とS_y[l..r] をswapする。
• hashクエリ(type = 2, x, y = 0, l, r): h(S_x[l..r]) を求め，出力する。

なお、

• 文字列 S に対し、S[l..r] を、Sのl文字目からr文字目まで(両端含む)の部分文字列を表すこととします。
• 英小文字 a に対し、ord(a) = 1, ord(b) = 2, ..., ord(z) = 26 とします。
• 文字列 S = c_1c_2...c_k に対し、\sum_{i=1..k} {\rm ord}(c_i)(1,000,000)^{i-1} を 10^9 + 7 で割ったあまりを h(S) とします。

制約

• 1 \leq N \leq 200,000
• 1 \leq M \leq 20
• S_i は英小文字のみからなる
• 1 \leq Q \leq 200,000
• type_i = 1, 2
• 1 \leq x_i \leq M
• swapクエリのとき, x_i < y_i \leq M
• hashクエリのとき、y_i = 0
• 1 \leq l_i \leq r_i \leq N

入力例 1

5 2
abcde
fghij
8
2 1 0 2 3
2 2 0 1 5
1 1 2 2 2
2 1 0 2 3
2 2 0 1 5
1 1 2 1 3
2 1 0 2 3
2 2 0 1 5

出力例 1

3000002
496944447
3000007
491944447
8000002
496979442

それぞれ、

• h("bc") = 3000002
• h("fghij") = 496944447
• h("gc") = 3000007
• h("fbhij") = 491944447
• h("bh") = 8000002
• h("agcij") = 496979442

を出力しています。

入力例 2

7 3
pzocuwt
ghqsktw
ogvyhak
13
2 1 0 1 2
1 1 2 5 6
1 1 3 3 6
1 2 3 4 5
1 2 3 5 6
1 1 2 1 6
1 1 2 5 6
2 2 0 5 5
2 1 0 2 3
1 2 3 1 4
1 1 2 2 7
2 3 0 1 6
2 3 0 1 4

出力例 2

26000016
21
17000008
556958241
25847241