M. Ahlan Ahlan bel3eed
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

While Obada was tidying up his house for the party, he found a word written by lowercase letters balloons. Obada loves palindromes, so he wants to make the word a palindrome. Obada can only reshuffle letters of a subarray $$$[L,R]$$$ of a string. But every now and then, Obada's brother changes a letter in the string. Obada found this an interesting problem and wants you to solve it.

Obada will give you a string $$$s$$$ of $$$n$$$ lowercase letters and $$$q$$$ queries of the following types:

  • "$$$1$$$ $$$i$$$ $$$c$$$" — set $$$s_i=c$$$.
  • "$$$2$$$ $$$L$$$ $$$R$$$" — Obada wonders how many different palindromic strings of length $$$n$$$ he could obtain from $$$s$$$ by reshuffling the letters in the subarray $$$[L,R]$$$. In other words, the number of different palindromic strings $$$s$$$ could become equal to by reshuffling those letters. Note that this type of query doesn't really change $$$s$$$. Since the answer might be very large, print it modulo $$$10^9+7$$$.

A palindrome is a string that reads the same backward as forward; for example, strings "z", "aaa", "aba", "abccba" are palindromes, but strings "ammar", "bassam", "ab" are not.

Can you solve this problem?

Input

The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases.

The first line of each testcase consists of two integers $$$n,q \: (1 \leq n,q \leq 10^5)$$$— the length of $$$s$$$ and the number of queries.

The second line of each test case contains the string $$$s$$$ of length $$$n$$$ containing only lowercase latin letters.

The next $$$q$$$ lines describe the queries, each line is like one of the following:

  • "$$$1$$$ $$$i$$$ $$$c$$$" $$$(1 \leq i \leq n)$$$ and $$$c$$$ is a lowercase latin letter.
  • "$$$2$$$ $$$L$$$ $$$R$$$" $$$(1 \leq L \leq R \leq n)$$$.

It is guaranteed that there will be at least one query of the second type in each testcase, and the sum of each of $$$n$$$ and $$$q$$$ over all testcases doesn't exceed $$$10^5$$$.

Output

For each query of the second type, print the number of different palindromic strings he could obtain from $$$s$$$ by reshuffling the letters in the subarray $$$[L,R]$$$, modulo $$$10^9+7$$$.

Example
Input
4
10 3
abcdecedba
2 6 8
1 10 b
2 6 8
10 5
abcdeabcde
2 1 10
2 1 5
1 1 e
1 2 d
2 3 8
3 4
aab
2 1 2
2 2 3
1 1 b
2 2 3
5 3
caabc
2 2 4
1 5 a
2 2 4
Output
1 0 
120 1 0 
0 1 1 
1 0