410301: GYM104003 I William and Array

Today is William's 26th birthday! As such, his friends have gifted him an array of length $$$N$$$. Since he is turning 26, the array will consist of only the 26 letters of the English alphabet ($$$\{\text{a}, \text{b}, \dots, \text{z}\}$$$). However, William's friends are super picky – they want the array to be perfect before they present it to William. Each of William's $$$Q$$$ friends have a chance to either make a change to the array by changing the letter at a certain index to a different English letter, or to inspect a contiguous subarray of the array and check how many palindromes the letters within the subarray can create. A palindrome is a string which is read the same forwards and backwards.

For example, if the array initially looks like $$$\{\text{q}, \text{q}, \text{r}, \text{a}, \text{r}\}$$$, and William has 2 friends, then William's first friend may choose to change the letter $$$\text{q}$$$ at index 1 to the letter $$$\text{a}$$$, resulting in the array becoming $$$\{\text{q}, \text{a}, \text{r}, \text{a}, \text{r}\}$$$, and his second friend might inspect the contiguous subarray starting at index 1 and ending at index 4 ($$$\{\text{a}, \text{r}, \text{a}, \text{r}\}$$$). The second friend will then realize that there exist 2 possible palindromes using exactly these letters ($$$\text{arra, raar}$$$). Note: when executing an inspection, the friend must use all of the letters in the range to construct palindromes.

Since William has many friends and each friend would like to perform one of these two types of queries (and because the array they are working with is very large), they need help doing all of the necessary computations. Please help them out!

The first line of input will contain two space-separated integers, $$$N\ (1 \leq N \leq 2 \cdot 10^5)$$$ and $$$Q\ (1 \leq Q \leq 2 \cdot 10^5)$$$, denoting the length of the array and the number of friends William has, respectively. The next line will consist of a single string of length $$$N$$$ consisting of lowercase English letters representing the initial state of the array. The next $$$Q$$$ lines will each begin with either a $$$1$$$ or a $$$2$$$. A $$$1$$$ represents a query of the first type, and will be followed by an integer $$$i\ (0 \leq i < N)$$$ and a lowercase English letter. This means that a friend would like to replace the letter currently at index $$$i$$$ with the given letter. A $$$2$$$ represents a query of the second type, and will be followed by two integers, $$$l\ (0 \leq l < N)$$$ and $$$r\ (l \leq r < N)$$$ denoting the start and end (inclusive) of a contiguous subarray that the current friend would like to inspect.

For each query of the second type, print a single line containing the number of palindromes which can be created using the letters found within the contiguous subarray that the friend would like to inspect. Since the answer to each query can be quite large, output each number modulo $$$10^9 + 7$$$. It is guaranteed that there will be at least one query of the second type.

5 5
bbbaa
2 0 4
1 1 b
2 2 4
1 2 c
2 1 2

2
1
0