Consider a lowercase English alphabetic letter character denoted by $\textbf{C}$. A shift operation on some $\textbf{C}$ turns it into the next letter in the alphabet. For example, and $shift(a)=b$, $shift(e)=f$, $shift(z)=a$ . 

Given a zero-indexed string, $\boldsymbol{\mathrm{~S~}}$, of $n$ lowercase letters, perform $\textit{q}$ queries on $\boldsymbol{\mathrm{~S~}}$ where each query takes one of the following two forms:

1 i j t: All letters in the inclusive range from $\boldsymbol{i}$ to $j$ are shifted $\boldsymbol{\boldsymbol{t}}$ times.  
2 i j: Consider all indices in the inclusive range from $\boldsymbol{i}$ to $j$. Find the number of non-empty subsets of characters, $c_1,c_2,\ldots,c_k$ where $i\leq\:\text{index of}\:c_1<\:\text{index of}\:c_2<\ldots<\:\text{index of}\:c_k\leq j)$, such that characters $c_1,c_2,c_3,\ldots,c_k$ can be rearranged to form a palindrome. Then print this number modulo $10^9+7$ on a new line. Two palindromic subsets are considered to be different if their component characters came from different indices in the original string.

Note
Two palindromic subsets are considered to be different if their component characters came from different indices in the original string.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ and $\textit{q}$. 

The second line contains a string of $n$ lowercase English alphabetic letters (i.e., a through z) denoting $\boldsymbol{\mathrm{~S~}}$. 

Each of the $\textit{q}$ subsequent lines describes a query in one of the two formats defined above.

Constraints

$1\leq n\leq10^5$  
$1\leq q\leq10^5$  
$0\leq i\leq j\lt n$ for each query.
$0\leq t\leq10^9$ for each query of type $1$.

Subtasks

For $20\%$ of the maximum score:  

$n\leq500$
$q\leq500$  

For another $30\%$ of the maximum score: 

All queries will be of type $2$. 

Output Format

For each query of type $2$ (i.e., 2 i j), print the number of non-empty subsets of characters satisfying the conditions given above, modulo $10^9+7$, on a new line.

Sample Input 0
3 5
aba
2 0 2
2 0 0
2 1 2
1 0 1 1
2 0 2

Sample Output 0
5
1
2
3

Explanation 0

We perform the following $q=5$ queries:

2 0 2: $s=\mathtt{aba}$ and we want to find the palindromic subsets of substring $\textbf{aba}$. There are five such subsets that form palindromic strings ($\mbox{a}$, $\mbox{b}$, $\mbox{a}$, $\textbf{aa}$, and $\textbf{aba}$), so we print the result of $5\ \text{mod}\ (10^9+7)=5$ on a new line
2 0 0: $s=\mathtt{aba}$ and we want to find the palindromic subsets of substring $\mbox{a}$. Because this substring only has one letter, we only have one subset forming a palindromic string ($\mbox{a}$). We then print the result of $1\:\text{mod}\:(10^9+7)=1$ on a new line. 
2 1 2:  $s=\mathtt{aba}$ and we want to find the palindromic subsets of substring $\textbf{ba}$. There are two such subsets that form palindromic strings ($\mbox{b}$ and $\mbox{a}$), so we print the result of $2\ \text{mod}\ (10^9+7)=2$ on a new line.  
1 0 1 1: $s=\mathtt{aba}$ and we need to perform $t=1$ shift operations on each character from index $i=\textbf{0}$ to index $j=1$. After performing these shifts, $s=\mathtt{b}\textbf{ca}$.  
2 0 2: $s=\mathtt{b}\textbf{ca}$ and we want to find the palindromic subsets of substring $\mathtt{b}\textbf{ca}$. There are three valid subsets that form palindromic strings ($\mbox{b}$, $\boldsymbol{\mathsf{C}}$, and $\mbox{a}$), so we print the result of $3\ \text{mod}\ (10^9+7)=3$ on a new line.

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import math
import os
import random
import re
import sys

class MyST:

	def __init__(self, s):
		orda = ord('a')
		self.slen = slen = len(s)
		self.depth = (slen - 1).bit_length()
		self.disp = 1 << self.depth
		self.arr = arr = memoryview(bytearray(4 * (2 * self.disp + 1))).cast('I')
		self.lazy = lazy = memoryview(bytearray(1 * (2 * self.disp + 1))).cast('B')
		for (i, c) in enumerate(s, self.disp):
			arr[i] = 1 << ord(c) - orda
		for i in range(self.disp - 1, 0, -1):
			arr[i] = arr[2 * i] | arr[2 * i + 1]

	def do_data_shift(self, node, shift):
		data = self.arr[node]
		self.arr[node] = (data << shift | data >> 26 - shift) & 67108863

	def propagate_lazy(self, node):
		lazy = self.lazy
		lazy_val = lazy[node]
		lazy[node] = 0
		node *= 2
		self.do_data_shift(node, lazy_val)
		lazy[node] += lazy_val
		lazy[node] %= 26
		node += 1
		self.do_data_shift(node, lazy_val)
		lazy[node] += lazy_val
		lazy[node] %= 26

	def rangeop(self, lo, hi, shift):
		shift %= 26
		if not shift:
			return
		lo += self.disp
		hi += self.disp
		self.update(lo, hi, 0, shift)

	def update(self, lo, hi, level, shift):
		levelup = self.depth - level
		lazy = self.lazy
		chunk = lo >> levelup
		(chunk_lo, chunk_hi) = (chunk << levelup, (chunk + 1 << levelup) - 1)
		if lo == chunk_lo and hi == chunk_hi:
			self.do_data_shift(chunk, shift)
			lazy[chunk] += shift
			lazy[chunk] %= 26
		else:
			if lazy[chunk]:
				self.propagate_lazy(chunk)
			pivot = 2 * chunk + 1 << levelup - 1
			if lo < pivot <= hi:
				self.update(lo, pivot - 1, level + 1, shift)
				self.update(pivot, hi, level + 1, shift)
			else:
				self.update(lo, hi, level + 1, shift)
			self.arr[chunk] = self.arr[2 * chunk] | self.arr[2 * chunk + 1]

	def rangequery(self, lo, hi):
		lo += self.disp
		hi += self.disp
		return self.query(lo, hi, 0)

	def query(self, lo, hi, level):
		levelup = self.depth - level
		lazy = self.lazy
		ret = 0
		chunk = lo >> levelup
		(chunk_lo, chunk_hi) = (chunk << levelup, (chunk + 1 << levelup) - 1)
		if lo == chunk_lo and hi == chunk_hi:
			ret |= self.arr[chunk]
		else:
			if lazy[chunk]:
				self.propagate_lazy(chunk)
			pivot = 2 * chunk + 1 << levelup - 1
			if lo < pivot <= hi:
				ret |= self.query(lo, pivot - 1, level + 1)
				ret |= self.query(pivot, hi, level + 1)
			else:
				ret |= self.query(lo, hi, level + 1)
		return ret
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
q = int(first_multiple_input[1])
s = input()
st = MyST(s)
MOD = 10 ** 9 + 7
RET = []
for q_itr in range(q):
	args = tuple(map(int, input().split()))
	if args[0] == 1:
		st.rangeop(*args[1:])
	elif args[0] == 2:
		bits = st.rangequery(*args[1:])
		bits = (bits & 1431655765) + ((bits & 2863311530) >> 1)
		bits = (bits & 858993459) + ((bits & 3435973836) >> 2)
		bits = (bits & 252645135) + ((bits & 4042322160) >> 4)
		bits = (bits & 16711935) + ((bits & 4278255360) >> 8)
		bits = (bits & 255) + ((bits & 16711680) >> 16)
		RET.append(((bits + 1) * pow(2, args[2] - args[1] + 1 - bits, MOD) - 1) % MOD)
	else:
		raise ValueError('wot??')
print('\n'.join(map(str, RET)))


import math
import os
import random
import re
import sys

class MyST:

	def __init__(self, s):
		orda = ord('a')
		self.slen = slen = len(s)
		self.depth = (slen - 1).bit_length()
		self.disp = 1 << self.depth
		self.arr = arr = memoryview(bytearray(4 * (2 * self.disp + 1))).cast('I')
		self.lazy = lazy = memoryview(bytearray(1 * (2 * self.disp + 1))).cast('B')
		for (i, c) in enumerate(s, self.disp):
			arr[i] = 1 << ord(c) - orda
		for i in range(self.disp - 1, 0, -1):
			arr[i] = arr[2 * i] | arr[2 * i + 1]

	def do_data_shift(self, node, shift):
		data = self.arr[node]
		self.arr[node] = (data << shift | data >> 26 - shift) & 67108863

	def propagate_lazy(self, node):
		lazy = self.lazy
		lazy_val = lazy[node]
		lazy[node] = 0
		node *= 2
		self.do_data_shift(node, lazy_val)
		lazy[node] += lazy_val
		lazy[node] %= 26
		node += 1
		self.do_data_shift(node, lazy_val)
		lazy[node] += lazy_val
		lazy[node] %= 26

	def rangeop(self, lo, hi, shift):
		shift %= 26
		if not shift:
			return
		lo += self.disp
		hi += self.disp
		self.update(lo, hi, 0, shift)

	def update(self, lo, hi, level, shift):
		levelup = self.depth - level
		lazy = self.lazy
		chunk = lo >> levelup
		(chunk_lo, chunk_hi) = (chunk << levelup, (chunk + 1 << levelup) - 1)
		if lo == chunk_lo and hi == chunk_hi:
			self.do_data_shift(chunk, shift)
			lazy[chunk] += shift
			lazy[chunk] %= 26
		else:
			if lazy[chunk]:
				self.propagate_lazy(chunk)
			pivot = 2 * chunk + 1 << levelup - 1
			if lo < pivot <= hi:
				self.update(lo, pivot - 1, level + 1, shift)
				self.update(pivot, hi, level + 1, shift)
			else:
				self.update(lo, hi, level + 1, shift)
			self.arr[chunk] = self.arr[2 * chunk] | self.arr[2 * chunk + 1]

	def rangequery(self, lo, hi):
		lo += self.disp
		hi += self.disp
		return self.query(lo, hi, 0)

	def query(self, lo, hi, level):
		levelup = self.depth - level
		lazy = self.lazy
		ret = 0
		chunk = lo >> levelup
		(chunk_lo, chunk_hi) = (chunk << levelup, (chunk + 1 << levelup) - 1)
		if lo == chunk_lo and hi == chunk_hi:
			ret |= self.arr[chunk]
		else:
			if lazy[chunk]:
				self.propagate_lazy(chunk)
			pivot = 2 * chunk + 1 << levelup - 1
			if lo < pivot <= hi:
				ret |= self.query(lo, pivot - 1, level + 1)
				ret |= self.query(pivot, hi, level + 1)
			else:
				ret |= self.query(lo, hi, level + 1)
		return ret
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
q = int(first_multiple_input[1])
s = input()
st = MyST(s)
MOD = 10 ** 9 + 7
RET = []
for q_itr in range(q):
	args = tuple(map(int, input().split()))
	if args[0] == 1:
		st.rangeop(*args[1:])
	elif args[0] == 2:
		bits = st.rangequery(*args[1:])
		bits = (bits & 1431655765) + ((bits & 2863311530) >> 1)
		bits = (bits & 858993459) + ((bits & 3435973836) >> 2)
		bits = (bits & 252645135) + ((bits & 4042322160) >> 4)
		bits = (bits & 16711935) + ((bits & 4278255360) >> 8)
		bits = (bits & 255) + ((bits & 16711680) >> 16)
		RET.append(((bits + 1) * pow(2, args[2] - args[1] + 1 - bits, MOD) - 1) % MOD)
	else:
		raise ValueError('wot??')
print('\n'.join(map(str, RET)))


import math
import os
import random
import re
import sys
mod = 1000000007
polys = [1]
maxLen = 100

class Node:

	def __init__(self, l, r):
		self.l = l
		self.r = r
		self.off = 0
		if r - l < maxLen:
			self.left = self.right = None
		else:
			mid = r + l >> 1
			self.left = Node(self.l, mid)
			self.right = Node(mid, self.r)
		self.mask = None

	def add(self, l, r, off):
		if self.r < l or r < self.l:
			return
		l = max(l, self.l)
		r = min(r, self.r)
		if l == r or off == 0:
			return
		if l == self.l and r == self.r and (self.left is not None):
			self.off += off
			self.off %= 26
		elif self.left is None:
			if off % 26 > 0 and (l > 0 or len(arr) != r):
				for i in range(l, r):
					arr[i] = (arr[i] + off) % 26
			self.mask = None
		else:
			self.left.add(l, r, off)
			self.right.add(l, r, off)

		def countPolyndroms(self, l, r):
			mask = self.getMask(l, r)
			counter = sum(mask)
			deg = r - l - counter
			while len(polys) <= deg:
				polys.append(polys[-1] * 2 % mod)
			res = (counter + 1) * polys[deg] - 1
			return res % mod

	def getMask(self, l, r):
		if self.r < l or r < self.l:
			return [0] * 26
		l = max(l, self.l)
		r = min(r, self.r)
		if self.left:
			lmask = self.left.getMask(l, r)
			if all(lmask):
				return lmask
			rmask = self.right.getMask(l, r)
			if all(rmask):
				return rmask
			res = [0] * 26
			for i in range(26):
				res[(i + self.off) % 26] = rmask[i] or lmask[i]
			return res
		if self.l == l and self.r == r:
			if self.mask is None:
				self.mask = [0] * 26
				for i in range(l, r):
					self.mask[arr[i]] = 1
			if self.off:
				res = [0] * 26
				for i in range(26):
					res[(i + self.off) % 26] = self.mask[i]
			else:
				res = self.mask
			return res
		mask = [0] * 26
		for i in range(l, r):
			mask[arr[i]] = 1
		return mask
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
q = int(first_multiple_input[1])
arr = [ord(c) - 97 for c in input()]
root = Node(0, len(arr))
for _ in range(q):
	qu = input().strip().split()
	l = int(qu[1])
	r = int(qu[2]) + 1
	if qu[0] == '1':
		t = int(qu[3])
		root.add(l, r, t)
	else:
		counter = sum(root.getMask(l, r))
		deg = r - l - counter
		while len(polys) <= deg:
			polys.append(polys[-1] * 2 % mod)
		print(((counter + 1) * polys[deg] - 1) % mod)