Madam Hannah Otto, the CEO of Reviver Corp., is fond of palindromes, or words that read the same forwards or backwards. She thinks palindromic brand names are appealing to millennials.  

As part of the marketing campaign for the company's new juicer called the Rotator™, Hannah decided to push the marketing team's palindrome-searching skills to a new level with a new challenge.  

In this challenge, Hannah provides a string $\boldsymbol{\mathrm{~S~}}$ consisting of lowercase English letters. Every day, for $\textit{q}$ days, she would select two integers $\boldsymbol{l}$ and $\textbf{r}$, take the substring ${\mbox{S}}_{\mbox{l}\ldots\mbox{r}}$ (the substring of $\boldsymbol{\mathrm{~S~}}$ from index $\boldsymbol{l}$ to index $\textbf{r}$), and ask the following question:

Consider all the palindromes that can be constructed from some of the letters from ${\mbox{S}}_{\mbox{l}\ldots\mbox{r}}$. You can reorder the letters as you need. Some of these palindromes have the maximum length among all these palindromes. How many maximum-length palindromes are there?  

For example, if $s=\textbf{madamimadam}$, $l=4$ and $r=7$, then we have,

Your job as the head of the marketing team is to answer all the queries. Since the answers can be very large, you are only required to find the answer modulo $10^9+7$.  

Complete the functions initialize and answerQuery and return the number of maximum-length palindromes modulo $10^9+7$. 

Input Format

The first line contains the string $\boldsymbol{\mathrm{~S~}}$.

The second line contains a single integer $\textit{q}$.

The $i^{th}$ of the next $\textit{q}$ lines contains two space-separated integers $\mathbf{l}_i$, $r_i$ denoting the $\boldsymbol{l}$ and $\textbf{r}$ values Anna selected on the $i^{th}$ day.  

Constraints

Here, $\left|s\right|$ denotes the length of $\boldsymbol{\mathrm{~S~}}$.  

$1\leq|s|\leq10^5$
$1\leq q\leq10^5$
$1\leq l_i\leq r_i\leq|s|$

Subtasks

For 30% of the total score:

$1\leq|s|\leq100$
$1\leq q\leq1000$
$r_i-l_i\leq3$

For 60% of the total score:

$1\leq|s|\leq100$
$1\leq q\leq1000$

Output Format

For each query, print a single line containing a single integer denoting the answer.

Sample Input 0
week
2
1 4
2 3

Sample Output 0
2
1

Explanation 0

On the first day, $l=1$ and $r=4$. The maximum-length palindromes are "ewe" and "eke".

On the second day, $l=2$ and $r=3$. The maximum-length palindrome is "ee".

Sample Input 1
abab
1
1 4

Sample Output 1
2

Explanation 1

Here, the maximum-length palindromes are "abba" and "baab".

Source: hackerrank | Difficulty: MEDIUM
Tags: String algorithms


Solutions:
from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


import sys, math
MOD = 10 ** 9 + 7
fact = [1]
cur = 1
for i in range(1, 6 * 10 ** 4):
	cur *= i
	cur %= MOD
	fact.append(cur)
alpha = 'abcdefghijklmnopqrstuvwxyz'
dp = [0]
dp2 = [[0] * 26]

def bitm(c):
	return 1 << alpha.find(c)

def initialize(s):
	cur = 0
	for c in s:
		tmp = [i for i in dp2[-1]]
		tmp[alpha.find(c)] += 1
		cur ^= bitm(c)
		dp.append(cur)
		dp2.append(tmp)

def modInv(x, pow=MOD - 2):
	if pow <= 3:
		return x ** pow % MOD
	else:
		tmp = modInv(x, pow // 2)
		tmp *= tmp
		tmp %= MOD
		if pow % 2 == 0:
			return tmp
		else:
			return tmp * x % MOD
mi = [modInv(fact[x]) for x in range(6 * 10 ** 4)]

def answerQuery(l, r):
	tmp = dp[l - 1] ^ dp[r]
	tmp2 = [(dp2[r][i] - dp2[l - 1][i]) // 2 for i in range(26)]
	possLetters = 0
	for c in range(26):
		if tmp & 1 << c:
			possLetters += 1
	middle = max(possLetters, 1)
	others = (r - l + 1 - possLetters) // 2
	ans = fact[others] * middle % MOD
	for i in tmp2:
		if i > 0:
			ans *= mi[i]
			ans %= MOD
	return ans
s = input().strip()
initialize(s)
q = int(input().strip())
for a0 in range(q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	result = answerQuery(l, r)
	print(result % MOD)


import collections
import functools
import sys
MOD = 1000000007
string = None
histogram = [[0] * 26]
factorial_cache = [1]
for i in range(1, 10 ** 5 + 1):
	factorial_cache.append(factorial_cache[-1] * i % MOD)

def mulinv(b, n):

	def egcd(b, n):
		(x0, x1, y0, y1) = (1, 0, 0, 1)
		while n != 0:
			(q, b, n) = (b // n, n, b % n)
			(x0, x1) = (x1, x0 - q * x1)
			(y0, y1) = (y1, y0 - q * y1)
		return (b, x0, y0)
	(g, x, _) = egcd(b, n)
	if g == 1:
		return x % n

def initialize(s):
	global string
	string = s
	for i in s:
		x = list(histogram[-1])
		x[ord(i) - ord('a')] += 1
		histogram.append(x)

def answerQuery(l, r):

	def count(counter):
		(c1, nl) = (sum((i & 1 for i in counter)), [i >> 1 for i in counter if i > 1])
		if c1 == 0:
			c1 = 1
		divisor = functools.reduce(lambda lhs, rhs: lhs * rhs % MOD, map(factorial_cache.__getitem__, nl), 1)
		return c1 * factorial_cache[sum(nl)] * mulinv(divisor, MOD) % MOD
	return count(list(map(lambda x, y: x - y, histogram[r], histogram[l - 1])))
s = input().strip()
initialize(s)
q = int(input().strip())
for a0 in range(q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	result = answerQuery(l, r)
	print(result)


mod = 10 ** 9 + 7
string = input().strip()
q = int(input())
array = [[0] * (len(string) + 1) for _ in range(26)]
fact_length = (len(string) + 2) // 2
fact = [1] * fact_length
fact_inv = [1] * fact_length

def initialize():
	for i in range(2, len(fact)):
		fact[i] = fact[i - 1] * i % mod
		fact_inv[i] = pow(fact[i], mod - 2, mod)
	for i in range(len(string)):
		affected = ord(string[i]) - ord('a')
		for j in range(26):
			array[j][i] += array[j][i - 1]
		array[affected][i] += 1
initialize()
for _ in range(q):
	(odd, even) = (0, [])
	(l, r) = [int(x) - 1 for x in input().split()]
	for i in range(26):
		count = array[i][r] - array[i][l - 1]
		odd += int(count & 1)
		even.append(count // 2)
	odd = max(odd, 1)
	total = fact[sum(even)] * odd
	for x in even:
		total *= fact_inv[x]
		total %= mod
	total %= mod
	print(total)


from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


import sys, math
MOD = 10 ** 9 + 7
fact = [1]
cur = 1
for i in range(1, 6 * 10 ** 4):
	cur *= i
	cur %= MOD
	fact.append(cur)
alpha = 'abcdefghijklmnopqrstuvwxyz'
dp = [0]
dp2 = [[0] * 26]

def bitm(c):
	return 1 << alpha.find(c)

def initialize(s):
	cur = 0
	for c in s:
		tmp = [i for i in dp2[-1]]
		tmp[alpha.find(c)] += 1
		cur ^= bitm(c)
		dp.append(cur)
		dp2.append(tmp)

def modInv(x, pow=MOD - 2):
	if pow <= 3:
		return x ** pow % MOD
	else:
		tmp = modInv(x, pow // 2)
		tmp *= tmp
		tmp %= MOD
		if pow % 2 == 0:
			return tmp
		else:
			return tmp * x % MOD
mi = [modInv(fact[x]) for x in range(6 * 10 ** 4)]

def answerQuery(l, r):
	tmp = dp[l - 1] ^ dp[r]
	tmp2 = [(dp2[r][i] - dp2[l - 1][i]) // 2 for i in range(26)]
	possLetters = 0
	for c in range(26):
		if tmp & 1 << c:
			possLetters += 1
	middle = max(possLetters, 1)
	others = (r - l + 1 - possLetters) // 2
	ans = fact[others] * middle % MOD
	for i in tmp2:
		if i > 0:
			ans *= mi[i]
			ans %= MOD
	return ans
s = input().strip()
initialize(s)
q = int(input().strip())
for a0 in range(q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	result = answerQuery(l, r)
	print(result % MOD)


import sys

def power(x, n, m):
	if n == 1:
		return x % m
	elif n == 0:
		return 1
	res = power(x, n // 2, m)
	if n % 2 == 0:
		return res * res % m
	else:
		return res * res * x % m

def initialize(s, factorials, invfacts, counts):
	characters = []
	n = len(s)
	for i in range(26):
		characters.append(chr(ord('a') + i))
	curindex = 0
	for c in s:
		curindex += 1
		for i in range(26):
			counts[i].append(0)
		counts[ord(c) - ord('a')][curindex] = 1
	for i in range(n):
		for j in range(26):
			counts[j][i + 1] += counts[j][i]
	MOD = 1000000007
	factorials.append(1)
	invfacts.append(1)
	for i in range(1, n // 2 + 3):
		curfact = factorials[i - 1] * i % MOD
		curinv = power(curfact, MOD - 2, MOD)
		factorials.append(curfact)
		invfacts.append(curinv)
	return

def answerQuery(l, r, factorials, invfacts, counts):
	MOD = 1000000007
	oddtotal = 0
	eventotal = 0
	total = 1
	for i in range(26):
		curcount = counts[i][r] - counts[i][l - 1]
		total = total * invfacts[curcount // 2] % MOD
		eventotal += curcount // 2
		oddtotal += curcount % 2
	if oddtotal == 0:
		oddtotal = 1
	total = total * factorials[eventotal] * oddtotal % MOD
	return total
s = input().strip()
factorials = []
invfacts = []
counts = []
for i in range(26):
	counts.append([0])
initialize(s, factorials, invfacts, counts)
q = int(input().strip())
for a0 in range(q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	result = answerQuery(l, r, factorials, invfacts, counts)
	print(result)


import sys
import copy

def initialize(s):
	n = len(s)
	d = [[] for i in range(n + 1)]
	d[0] = [0] * 26
	curr_arr = d[0]
	for idx in range(1, n + 1):
		curr_arr = copy.copy(curr_arr)
		curr_arr[ord(s[idx - 1]) - ord('a')] += 1
		d[idx] = curr_arr
	return d
mem = {2: 2}

def nChooseArr(arr):
	k = 1000000007
	n = sum(arr)
	numerator = 1
	denominator = 1
	for i in range(n, 1, -1):
		if i in mem:
			numerator = numerator * mem[i] % k
			mem[n] = numerator
			break
		numerator *= i
		if numerator > k:
			numerator = numerator % k
	for idx in range(26):
		temp = 1
		for j in range(arr[idx], 1, -1):
			if j in mem:
				temp = temp * mem[j] % k
				mem[arr[idx]] = temp
				break
			temp *= j
			if temp > k:
				temp = temp % k
		denominator = denominator * temp % k
	inv_denom = pow(denominator, k - 2, k)
	res = numerator * inv_denom % k
	return res

def answerQuery(l, r, d):
	k = 1000000007
	curr_arr = [0] * 26
	arr_l = d[l - 1]
	arr_r = d[r]
	for idx in range(26):
		curr_arr[idx] = arr_r[idx] - arr_l[idx]
	flag = False
	new_arr = copy.copy(curr_arr)
	new_arr_odd = copy.copy(curr_arr)
	for idx in range(26):
		new_arr[idx] = curr_arr[idx] // 2
		new_arr_odd[idx] = curr_arr[idx] % 2
	res = nChooseArr(new_arr) * max(1, sum(new_arr_odd))
	return res % k
s = input().strip()
d = initialize(s)
q = int(input().strip())
for a0 in range(q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	result = answerQuery(l, r, d)
	print(result)


import sys
from collections import Counter
from functools import lru_cache
from math import factorial

def initialize(s):
	stats = [[0] * 26]
	for c in s:
		cc = list(stats[-1])
		cc[ord(c) - 97] += 1
		stats.append(cc)
	factorials = [1]
	inverse_factorials = [1]
	for i in range(1, 10 ** 5 + 1):
		factorials.append(factorials[-1] * i % (10 ** 9 + 7))
		inverse_factorials.append(pow(factorials[-1], 10 ** 9 + 5, 10 ** 9 + 7))
	return (stats, factorials, inverse_factorials)

def answerQuery(l, r, stats, factorials, inverse_factorials):
	rr = stats[r][:]
	for i in range(26):
		rr[i] -= stats[l - 1][i]
	odd = 0
	for i in range(26):
		if rr[i] % 2 == 1:
			odd += 1
			rr[i] -= 1
	s = sum(rr) // 2
	res = odd or 1
	rr.sort(reverse=True)
	f = factorials[s]
	for x in rr:
		f = f * inverse_factorials[x // 2] % (10 ** 9 + 7)
	return res * f % (10 ** 9 + 7)
s = input().strip()
stats = initialize(s)
q = int(input().strip())
for a0 in range(q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	result = answerQuery(l, r, *stats)
	print(result)


max = 100005
mod = 1000000007
fact = [0] * max
inv = [0] * max
fact[0] = 1
for i in range(1, max):
	fact[i] = i * fact[i - 1] % mod

def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		print("Inverse doesn't exist")
	else:
		return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for i in range(max):
	inv[i] = modInverse(fact[i], mod)
s = list(input())
n = len(s)
s2 = [[0] * 26 for i in range(n)]
s2[0][ord(s[0]) - ord('a')] += 1
for i in range(1, n):
	for j in range(26):
		s2[i][j] += s2[i - 1][j]
	s2[i][ord(s[i]) - ord('a')] += 1
num = int(input())
for _ in range(num):
	(l, r) = map(int, input().split(' '))
	(l, r) = (l - 1, r - 1)
	cone = 0
	ctwo = 0
	ans = 1
	c = [0] * 26
	for i in range(26):
		c[i] = s2[r][i]
		if l > 0:
			c[i] -= s2[l - 1][i]
		if c[i] % 2 == 1:
			cone += 1
			c[i] -= 1
		c[i] = int(c[i] / 2)
		ctwo += c[i]
		ans = ans * inv[c[i]] % mod
	ans = ans * fact[ctwo] % mod
	if cone > 0:
		ans *= cone
	ans %= mod
	print(ans)


import sys, math
MOD = 10 ** 9 + 7
fact = [1]
cur = 1
for i in range(1, 6 * 10 ** 4):
	cur *= i
	cur %= MOD
	fact.append(cur)
alpha = 'abcdefghijklmnopqrstuvwxyz'
dp = [0]
dp2 = [[0] * 26]

def bitm(c):
	return 1 << alpha.find(c)

def initialize(s):
	cur = 0
	for c in s:
		tmp = [i for i in dp2[-1]]
		tmp[alpha.find(c)] += 1
		cur ^= bitm(c)
		dp.append(cur)
		dp2.append(tmp)

def modInv(x, pow=MOD - 2):
	if pow <= 3:
		return x ** pow % MOD
	else:
		tmp = modInv(x, pow // 2)
		tmp *= tmp
		tmp %= MOD
		if pow % 2 == 0:
			return tmp
		else:
			return tmp * x % MOD
mi = [modInv(fact[x]) for x in range(6 * 10 ** 4)]

def answerQuery(l, r):
	tmp = dp[l - 1] ^ dp[r]
	tmp2 = [(dp2[r][i] - dp2[l - 1][i]) // 2 for i in range(26)]
	possLetters = 0
	for c in range(26):
		if tmp & 1 << c:
			possLetters += 1
	middle = max(possLetters, 1)
	others = (r - l + 1 - possLetters) // 2
	ans = fact[others] * middle % MOD
	for i in tmp2:
		if i > 0:
			ans *= mi[i]
			ans %= MOD
	return ans
s = input().strip()
initialize(s)
q = int(input().strip())
for a0 in range(q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	result = answerQuery(l, r)
	print(result % MOD)


import sys
from collections import Counter
from functools import reduce
from math import factorial

def modular_inverse(a, m):
	m0 = m
	y = 0
	x = 1
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def ways(evens, odds, permutations, m, factorials, inverse_factorials):
	a = factorials[evens]
	ways = reduce(lambda x, y: x * inverse_factorials[y] % m, permutations, a) % m
	if odds > 0:
		ways *= odds % m
	return ways % m

def initialize(s):
	counters = [[0] * 26 for i in range(len(s) + 1)]
	for (i, c) in enumerate(map(ord, s)):
		for j in range(26):
			counters[i + 1][j] = counters[i][j]
		k = c - ord('a')
		counters[i + 1][k] = counters[i][k] + 1
	factorials = [1, 1]
	for i in range(2, len(s) + 1):
		factorials.append(factorials[i - 1] * i % (10 ** 9 + 7))
	inverse_factorials = []
	for f in factorials:
		inverse_factorials.append(modular_inverse(f, 10 ** 9 + 7))
	return (factorials, inverse_factorials, counters)

def answerQuery(l, r, counters, factorials, inverse_factorials):
	l_counter = counters[l - 1]
	r_counter = counters[r]
	evens = 0
	odds = 0
	permutations = []
	for (c1, c2) in zip(l_counter, r_counter):
		v = c2 - c1
		if v == 0:
			continue
		p = v // 2
		evens += p
		odds += 0 if v % 2 == 0 else 1
		if p > 1:
			permutations.append(p)
	return ways(evens, odds, permutations, 10 ** 9 + 7, factorials, inverse_factorials)
s = input()
(factorials, inverse_factorials, counters) = initialize(s)
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	result = answerQuery(l, r, counters, factorials, inverse_factorials)
	print(result)


import sys
from collections import defaultdict as dd
MOD = int(10 ** 9 + 7)
MAX_N = 10 ** 5
FACTORIAL = [0] * MAX_N
INV_FACTORIAL = [0] * MAX_N
FACTORIAL[0] = 1
INV_FACTORIAL[0] = 1
for n in range(1, MAX_N):
	FACTORIAL[n] = FACTORIAL[n - 1] * n % MOD
	INV_FACTORIAL[n] = pow(FACTORIAL[n], MOD - 2, MOD)

def warn(*args, **kwargs):
	pass

def get_int():
	return int(input())

def get_ints():
	return [int(x) for x in input().split()]

def binomial(n, k, mod):
	num = FACTORIAL[n]
	inv_denom = INV_FACTORIAL[k] * INV_FACTORIAL[n - k] % MOD
	return num * inv_denom % MOD

def distinct_permutations(char_counts):
	length = sum(char_counts)
	dp = 1
	for cnt in char_counts[:-1]:
		dp = dp * binomial(length, cnt, MOD) % MOD
		length -= cnt
	return dp

def max_palindrome_count(counts):
	half = []
	odd = []
	for (c, cnt) in counts.items():
		if cnt % 2 == 0:
			half.append(cnt // 2)
		else:
			odd.append(cnt)
	palindroms = 1
	if len(odd) > 0:
		palindroms *= len(odd)
		for cnt in odd:
			if cnt - 1 > 0:
				half.append((cnt - 1) // 2)
	palindroms *= distinct_permutations(half)
	return palindroms % MOD

def main():
	string = input().strip()
	test_cases = get_int()
	counts_total = {}
	cur_cnt = {}
	l = len(string)
	for c in set(string):
		counts_total[c] = [0] * (l + 1)
		cur_cnt[c] = 0
	for i in range(l):
		cur_cnt[string[i]] += 1
		for (char, cnt) in cur_cnt.items():
			counts_total[char][i] = cnt
	for _ in range(test_cases):
		(l, r) = get_ints()
		s = string[l - 1:r]
		warn('looking for max len palindromes in ', s)
		counts = {}
		for char in counts_total:
			cnt = counts_total[char][r - 1] - counts_total[char][l - 2]
			if cnt > 0:
				counts[char] = cnt
		print(max_palindrome_count(counts))
		warn('-' * 78)
main()


import math
import os
import random
import re
import sys
from collections import Counter
from math import factorial
f = [1 for _ in range(10 ** 5 + 1)]
mod = 10 ** 9 + 7
for i in range(1, 10 ** 5 + 1):
	f[i] = f[i - 1] * i % mod
inv_f = f[:]
inv_f[-1] = pow(f[-1], mod - 2, mod)
for i in range(10 ** 5 - 1, 0, -1):
	inv_f[i] = inv_f[i + 1] * (i + 1) % mod

def initialize(s):
	c = Counter()
	dp = []
	for ch in s:
		c[ch] += 1
		dp.append({k: v for (k, v) in c.items()})
	return dp

def fac(evens, mod):
	s = sum(evens)
	res = f[s]
	for v in evens:
		res *= inv_f[v]
	return res % mod

def answerQuery(dp, l, r):
	mod = 10 ** 9 + 7
	d = dp[l - 1] if l else {}
	ans = [v - d.get(c, 0) for (c, v) in dp[r].items()]
	evens = [x // 2 for x in ans if x > 1]
	odds = max(sum((1 for x in ans if x % 2 == 1)), 1)
	return odds * fac(evens, mod) % mod
s = input()
dp = initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(dp, l - 1, r - 1)
	print(result)


import sys, math
MOD = 10 ** 9 + 7
fact = [1]
cur = 1
for i in range(1, 6 * 10 ** 4):
	cur *= i
	cur %= MOD
	fact.append(cur)
alpha = 'abcdefghijklmnopqrstuvwxyz'
dp = [0]
dp2 = [[0] * 26]

def bitm(c):
	return 1 << alpha.find(c)

def initialize(s):
	cur = 0
	for c in s:
		tmp = [i for i in dp2[-1]]
		tmp[alpha.find(c)] += 1
		cur ^= bitm(c)
		dp.append(cur)
		dp2.append(tmp)

def modInv(x, pow=MOD - 2):
	if pow <= 3:
		return x ** pow % MOD
	else:
		tmp = modInv(x, pow // 2)
		tmp *= tmp
		tmp %= MOD
		if pow % 2 == 0:
			return tmp
		else:
			return tmp * x % MOD
mi = [modInv(fact[x]) for x in range(6 * 10 ** 4)]

def answerQuery(l, r):
	tmp = dp[l - 1] ^ dp[r]
	tmp2 = [(dp2[r][i] - dp2[l - 1][i]) // 2 for i in range(26)]
	possLetters = 0
	for c in range(26):
		if tmp & 1 << c:
			possLetters += 1
	middle = max(possLetters, 1)
	others = (r - l + 1 - possLetters) // 2
	ans = fact[others] * middle % MOD
	for i in tmp2:
		if i > 0:
			ans *= mi[i]
			ans %= MOD
	return ans
s = input().strip()
initialize(s)
q = int(input().strip())
for a0 in range(q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	result = answerQuery(l, r)
	print(result % MOD)


import math
import os
import random
import re
import sys
MOD = 10 ** 9 + 7

def generateFactorial(n):
	result = [0] * n
	result[0] = 1 % MOD
	for i in range(1, n):
		result[i] = result[i - 1] * i % MOD
	return result

def generateReverse(n):
	result = [0] * n
	if n > 1:
		result[1] = 1
	for i in range(2, n):
		result[i] = (MOD - MOD // i * result[MOD % i] % MOD) % MOD
	return result

def generateReverseFactorial(n):
	result = generateReverse(n)
	result[0] = 1
	for i in range(1, n):
		result[i] = result[i] * result[i - 1] % MOD
	return result

def combine(n, k):
	if k < 0 or k > n:
		return 0
	return factorial[n] * reverseFactorial[k] % MOD * reverseFactorial[n - k] % MOD

def initialize(s):
	n = len(s)
	global quantity
	quantity = [[0] * 26] * (n + 1)
	for i in range(n):
		quantity[i + 1] = quantity[i][:]
		quantity[i + 1][ord(s[i]) - ord('a')] += 1
	global factorial
	factorial = generateFactorial(n)
	global reverseFactorial
	reverseFactorial = generateReverseFactorial(n)

def answerQuery(l, r):
	odd = 0
	total = 0
	answer = 1
	for i in range(26):
		num = quantity[r][i] - quantity[l - 1][i]
		total += num >> 1
		answer *= combine(total, num >> 1)
		answer %= MOD
		odd += num & 1
	answer *= max(1, odd)
	answer %= MOD
	return answer
s = input()
initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


MOD = 10 ** 9 + 7
b = 'abcdefghijklmnopqrstuvwxyz'
s = input().strip()
x = (0,) * len(b)
a = [x]
d = {v: i for (i, v) in enumerate(b)}
f = [1]
inv = [0] * 100001
for i in range(1, 100000):
	f.append(f[-1] * i % MOD)

def inv_f(i):
	if not inv[i]:
		inv[i] = pow(f[i], MOD - 2, MOD)
	return inv[i]
for v in s:
	i = d[v]
	x = x[:i] + (x[i] + 1,) + x[i + 1:]
	a.append(x)
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	l -= 1
	c = [j - i for (i, j) in zip(a[l], a[r]) if i != j]
	o = sum((i & 1 for i in c))
	c = [i // 2 for i in c if i > 1]
	e = sum(c)
	ans = f[e]
	for i in c:
		ans = inv_f(i) * ans % MOD
	if o:
		ans = ans * o % MOD
	print(ans)


import math
import os
import random
import re
import sys
import array
p = 1000000007
maxs = 10000

def egcd(a, b):
	(x, y, u, v, bb) = (0, 1, 1, 0, b)
	while b != 0:
		q = a // b
		(a, b) = (b, a % b)
		(x, u) = (u - q * x, x)
		(y, v) = (v - q * y, y)
	return u if u > 0 else u + bb
f = [1]
invf = [1]
let = [0] * 26

def initialize(s):
	for i in range(1, len(s) + 1):
		f.append(f[-1] * i % p)
		invf.append(egcd(f[-1], p))
	for (i, c) in enumerate(s):
		let.extend(let[-26:])
		let[-26 + ord(c) - ord('a')] += 1

def answerQuery(l, r):
	d = [let[r * 26 + i] - let[(l - 1) * 26 + i] for i in range(26)]
	se = sum((x // 2 for x in d))
	so = sum((x % 2 for x in d)) or 1
	ff = f[se]
	for x in d:
		ff = ff * invf[x // 2] % p
	return ff * so % p
s = input()
initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


import math
import os
import random
import re
import sys
MOD = 10 ** 9 + 7
alphabet = 'abcdefghijklmnopqrstuvwxyz'
count = {c: [0] for c in alphabet}
fact = [1]

def initialize(s):
	for c in s:
		for c_ in alphabet:
			count[c_].append(count[c_][-1] + (1 if c == c_ else 0))
	for n in range(1, len(s) + 1):
		fact.append(fact[-1] * n % MOD)

def gcde(a, b):
	(r, u, v, r2, u2, v2) = (a, 1, 0, b, 0, 1)
	while r2 > 0:
		q = r // r2
		(r, u, v, r2, u2, v2) = (r2, u2, v2, r - q * r2, u - q * u2, v - q * v2)
	return (r, u, v)

def invMod(a, m):
	(r, u, v) = gcde(a, m)
	if r != 1:
		return None
	return u

def answerQuery(l, r):
	total = 0
	divisor = 1
	unique = 0
	for c in alphabet:
		(n, nr) = divmod(count[c][r] - count[c][l - 1], 2)
		unique += nr
		total += n
		divisor *= fact[n]
	return fact[total] * invMod(divisor, MOD) * max(1, unique) % MOD
s = input()
initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


import math
import os
import random
import re
import sys

def initialize(s):
	n = len(s)
	global facts
	facts = [1] * (n + 1)
	global st
	st = []
	for i in range(26):
		st.append([0] * (n + 1))
	for i in range(1, n + 1):
		facts[i] = facts[i - 1] * i % 1000000007
		ch = s[i - 1]
		k = ord(ch) - 97
		for j in range(26):
			st[j][i] = st[j][i - 1] + int(k == j)
	return

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def fact(x):
	r = 1
	for i in range(2, x + 1):
		r = r * i
		if r > 1000000007:
			r = r % 1000000007
	return r

def answerQuery(l, r):
	pairs = []
	singles = 0
	for j in range(26):
		i = st[j][r] - st[j][l - 1]
		t = i // 2
		if t > 0:
			pairs.append(t)
		if i % 2 == 1:
			singles += 1
	res = facts[sum(pairs)]
	res_inv = 1
	for p in pairs:
		res_inv = res_inv * facts[p] % 1000000007
	res_inv = modInverse(res_inv, 1000000007)
	res = res * res_inv % 1000000007
	if singles > 0:
		res = res * singles % 1000000007
	return res

def answerQueryOld(l, r):
	s = st[l - 1:r]
	ch_cnt = [0] * 26
	for ch in s:
		ch_cnt[ord(ch) - 97] += 1
	pairs = []
	singles = 0
	for i in ch_cnt:
		t = i // 2
		if t > 0:
			pairs.append(t)
		if i % 2 == 1:
			singles += 1
	res = math.factorial(sum(pairs))
	for p in pairs:
		res = res // math.factorial(p)
	if singles > 0:
		res = res * singles
	return res % 1000000007
s = input()
initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


import math
import os
import random
import re
import sys
from collections import Counter
from copy import copy

def initialize(s):
	global a, m, f, inv
	(m, f, inv) = (1000000007, [1], {})
	for i in range(1, 100000):
		f.append(f[-1] * i % m)
	a = [Counter()]
	for x in s:
		d = copy(a[-1])
		d[x] += 1
		a.append(d)

def recurse(a, b):
	if a == 0:
		return (0, 1)
	else:
		(y, x) = recurse(b % a, a)
		return (x - b // a * y, y)

def invf(a):
	global inv
	if a in inv:
		return inv[a]
	(x, y) = recurse(a, m)
	inv[a] = x % m
	return x % m

def answerQuery(l, r):
	d = Counter()
	for x in a[r]:
		d[x] += a[r][x]
	for x in a[l - 1]:
		d[x] -= a[l - 1][x]
	(o, r, t) = (0, 1, 0)
	for (k, v) in d.items():
		if v & 1:
			o += 1
		r *= invf(f[v // 2])
		t += v // 2
		r %= m
	return max(1, o) * r * f[t] % m
s = input()
initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


import sys
from time import time

class Cache:

	def __init__(self, s):
		self.rows = ord('z') - ord('a') + 1
		self.cols = len(s) + 1
		self.data = [None] * self.rows * self.cols
		for r in range(self.rows):
			self.set(r, 0, 0)
		for (c, ch) in enumerate(s):
			j = ord(ch) - ord('a')
			for r in range(0, self.rows):
				v = self.get(r, c)
				if r == j:
					v += 1
				self.set(r, c + 1, v)

	def index(self, r, c):
		return r * self.cols + c

	def get(self, r, c):
		return self.data[self.index(r, c)]

	def set(self, r, c, v):
		self.data[self.index(r, c)] = v

def modinv(n, p):
	return pow(n, p - 2, p)

def f_gen(p):
	(f, i) = (1, 0)
	while True:
		yield (f, modinv(f, p))
		i += 1
		f *= i
		f %= p

def frf_cache(n, p):
	(ff, rff) = ([], [])
	for (i, (f, rf)) in enumerate(f_gen(p)):
		ff.append(f)
		rff.append(rf)
		if i == n:
			break
	return (ff, rff)

def binomial(n, k, p, ff, rff):
	rval = ff[n] * rff[k]
	rval %= p
	rval *= rff[n - k]
	rval %= p
	return rval

def calc(vv, ones, p, ff, rff):
	rval = 1
	l = sum(vv)
	for v in vv:
		rval *= binomial(l, v, p, ff, rff)
		rval %= p
		l -= v
	if ones:
		rval *= ones
		rval %= p
	return rval

def solve(fr, to, m, cache, ff, rff):
	(vv, ones) = ([], 0)
	for r in range(cache.rows):
		v = cache.get(r, to) - cache.get(r, fr)
		if v > 1:
			vv.append(v // 2)
		if v % 2 == 1:
			ones += 1
	return calc(vv, ones, m, ff, rff)
tm = time()
m = pow(10, 9) + 7
N = pow(10, 5)
(ff, rff) = frf_cache(N, m)
print('factorial cache generated: %s' % (time() - tm,), file=sys.stderr)
print('ff=%s\nrff=%s' % (ff[:10], rff[:10]), file=sys.stderr)
s = input()
cache = Cache(s)
print('cache generated: %s' % (time() - tm,), file=sys.stderr)
n = int(input())
for _ in range(n):
	(fr, to) = map(int, input().split())
	print(solve(fr - 1, to, m, cache, ff, rff))
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


from collections import Counter
from functools import reduce, lru_cache
from operator import mul
M = 10 ** 9 + 7
MAX = 50001
FAC_M = [1] * MAX
for n in range(1, MAX):
	FAC_M[n] = n * FAC_M[n - 1] % M

@lru_cache(None)
def modular_inv(n, prime):
	if n <= 1:
		return 1
	return modular_inv(prime % n, prime) * (prime - prime // n) % prime

def get_counts(s):
	counts = [None for _ in range(len(s))]
	for (i, c) in enumerate(s):
		o = ord(c) - 97
		if i == 0:
			counts[i] = [0] * 26
			counts[i][o] = 1
		else:
			counts[i] = counts[i - 1][:]
			counts[i][o] += 1
	counts.append([0] * 26)
	return counts

def maxpali(l, r, counts):
	cs = [counts[r][i] - counts[l - 1][i] for i in range(26)]
	evens = [v // 2 for v in cs if v >= 2]
	odd = sum((1 for v in cs if v % 2 == 1))
	p = FAC_M[sum(evens)]
	q = reduce(mul, map(FAC_M.__getitem__, evens)) % M if evens else 1
	return p * modular_inv(q, M) * max(1, odd) % M
s = input()
q = int(input())
counts = get_counts(s)
for _ in range(q):
	(l, r) = map(int, input().split())
	print(maxpali(l - 1, r - 1, counts))


import math
import os
import random
import re
import sys
import math
from functools import wraps

def my_cache(func):
	cache = {}

	def set(key, val):
		cache[key] = val

	@wraps(func)
	def wrapper(*args, **kwargs):
		key = hash(args)
		if key in cache:
			return cache.get(key)
		else:
			val = func(*args, **kwargs)
			set(key, val)
			return val
	return wrapper

def ordered_cache(func):
	cache = {}

	def set(key, val):
		cache[key] = val

	@wraps(func)
	def wrapper(x):
		key = x
		if key in cache:
			return cache.get(key)
		else:
			max_current = max(list(cache.keys()) + [0])
			for i in range(max_current + 1, x):
				set(i, func(i))
			val = func(x)
			set(x, val)
			return val
	return wrapper

@ordered_cache
def fact(x):
	if x == 0:
		return 1
	else:
		return x * fact(x - 1) % (10 ** 9 + 7)

@my_cache
def exp(x, n):
	if n < 0:
		return exp(1 / x, -n) % (10 ** 9 + 7)
	elif n == 0:
		return 1
	elif n == 1:
		return x % (10 ** 9 + 7)
	elif n % 2 == 0:
		return exp(x * x % (10 ** 9 + 7), n / 2) % (10 ** 9 + 7)
	else:
		return x * exp(x * x % (10 ** 9 + 7), (n - 1) / 2) % (10 ** 9 + 7) % (10 ** 9 + 7)

@my_cache
def mod_inverse(x):
	return exp(x, 10 ** 9 + 5) % (10 ** 9 + 7)

def initialize(s):
	index = [tuple((0 for i in range(26)))]
	for i in range(0, len(s)):
		val = ord(s[i]) - 97
		prev = index[i]
		new_tup = tuple((prev[j] + 1 if j == val else prev[j] for j in range(26)))
		index.append(new_tup)
	return index

def answerQuery(l, r, index):
	frequencies = tuple([index[r][i] - index[l - 1][i] for i in range(26)])
	odds = max(1, sum([1 if x % 2 == 1 else 0 for x in frequencies]))
	pairs = [x // 2 for x in frequencies if x >= 2]
	offset = 0
	product = 1
	product = product * fact(sum(pairs)) % (10 ** 9 + 7)
	for pair in pairs:
		product = product * mod_inverse(fact(pair)) % (10 ** 9 + 7)
		offset += pair
	product = product * odds % (10 ** 9 + 7)
	return int(product)
s = input()
index = initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r, index)
	print(result)


from itertools import islice
M = 10 ** 9 + 7
min_code = ord('a')

def egcd(a, b):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while b != 0:
		(q, a, b) = (a // b, b, a % b)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (a, x0, y0)

def inverse(a, mod):
	(g, x, y) = egcd(a, mod)
	return x

def index(letter):
	return ord(letter) - min_code

def prepare_fact(size, M):
	cache = [None] * (size + 1)
	cache[0] = 1
	for i in range(1, len(cache)):
		cache[i] = cache[i - 1] * i % M
	return cache

def initialize(s):
	counts = [None] * (index('z') + 1)
	for i in range(len(counts)):
		counts[i] = [0] * len(s)
	counts[index(s[0])][0] = 1
	for (i, sym) in islice(enumerate(s), 1, None):
		for c in range(len(counts)):
			counts[c][i] = counts[c][i - 1]
		counts[index(sym)][i] += 1
	return counts

def answerQuery(counts, fact, l, r):
	odds = 0
	for i in range(len(counts)):
		upper = counts[i][r - 1]
		lower = counts[i][l - 2] if l > 1 else 0
		odds += int((upper - lower) % 2 == 1)
	pairs = (r - l + 1 - odds) // 2
	orders = fact[pairs]
	divisor = 1
	for i in range(len(counts)):
		upper = counts[i][r - 1]
		lower = counts[i][l - 2] if l > 1 else 0
		divisor = divisor * fact[(upper - lower) // 2] % M
	orders = orders * inverse(divisor, M) % M
	return orders * max(odds, 1) % M
s = input()
fact = prepare_fact(len(s), M)
counts = initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(counts, fact, l, r)
	print(result)


import math
import os
import random
import re
import sys
from functools import reduce
bigN = 1000000007

def str2array(s):
	ar2 = [[0] * 26 for ii in range(1 + len(s))]
	s_asInt = [ord(ch) - 97 for ch in s]
	for dex in range(len(s_asInt)):
		ar2[1 + dex] = [ar2[dex][jj] for jj in range(26)]
		ar2[1 + dex][s_asInt[dex]] += 1
	return ar2

def binaryExpansion(a):
	remainder = a
	expansion = []
	while remainder:
		expansion.append(remainder % 2)
		remainder = remainder // 2
	return expansion

def precomputeFactorials(n):
	factorialDict = {0: 1, 1: 1}
	invFactorialDict = {0: 1, 1: 1}
	binary_bigNminus2 = binaryExpansion(bigN - 2)
	for jj in range(2, 1 + n):
		factorialDict[jj] = jj * factorialDict[jj - 1] % bigN
		a = factorialDict[jj]
		a_toPower_2totheDex = [a]
		while len(a_toPower_2totheDex) < len(binary_bigNminus2):
			a_toPower_2totheDex.append(a_toPower_2totheDex[-1] * a_toPower_2totheDex[-1] % bigN)
		tempProduct = 1
		for dex in range(len(binary_bigNminus2)):
			if binary_bigNminus2[dex]:
				tempProduct = tempProduct * a_toPower_2totheDex[dex] % bigN
		invFactorialDict[jj] = tempProduct
	return [factorialDict, invFactorialDict]

def answerQuery(ar2, l, r, factorialDict, invFactorialDict):
	[arL, arR] = [ar2[l - 1], ar2[r]]
	L = [arR[ii] - arL[ii] for ii in range(26)]
	numOddValues = sum([el % 2 for el in L])
	BE = [el // 2 for el in L]
	BE = [el for el in BE if el != 0]
	numPermutations_BE = factorialDict[sum(BE)]
	for el in BE:
		numPermutations_BE = numPermutations_BE * invFactorialDict[el] % bigN
	totalPerms = numPermutations_BE * max(1, numOddValues) % bigN
	return totalPerms
s = input()
ar2 = str2array(s)
q = int(input())
[factorialDict, invFactorialDict] = precomputeFactorials(len(s))
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(ar2, l, r, factorialDict, invFactorialDict)
	print(result)


import math
import os
import random
import re
import sys
from collections import defaultdict
s = ''
M = 1000000007

def initialize(S):
	global s
	s = S
	pre_populate_fact_table(len(s) // 2, M)
	pre_calculate_frequencies(s)
debug = False

def dummy_print(*args):
	pass
if debug:
	printd = print
else:
	printd = dummy_print

def fast_power(a, p, M):
	if p == 1:
		return a
	if p == 0:
		return 1
	if p % 2 == 0:
		num = fast_power(a, p // 2, M) % M
		return num * num % M
	else:
		return a * fast_power(a, p - 1, M) % M
fact_cache = {}

def cached_factorial_mod(a, M):
	if a in fact_cache:
		return fact_cache[a]
	f = 1
	for i in range(1, a + 1):
		f = f * i % M
	fact_cache[a] = f
	return f

def pre_populate_fact_table(a, M):
	f = 1
	for i in range(1, a + 1):
		f = f * i % M
		fact_cache[i] = f
letter_freq = []

def pre_calculate_frequencies(s):
	running_freq = [0] * 26
	letter_freq.append(list(running_freq))
	for i in s:
		running_freq[ord(i) - ord('a')] += 1
		letter_freq.append(list(running_freq))

def calc_frequencies_at(l, r):
	a = letter_freq[l - 1]
	b = letter_freq[r]
	return [b[i] - a[i] for i in range(26)]

def answerQuery(l, r):
	printd('=====')
	ss = s[l - 1:r]
	printd(ss)
	permutations = 1
	factorial_bottom = 1
	factorial_top = 1
	total_letter_pairs = 0
	single_letters = 0
	letter_freq = calc_frequencies_at(l, r)
	for v in letter_freq:
		letter_pairs = v // 2
		single_letters += v % 2
		if letter_pairs:
			printd('letter_pairs', letter_pairs)
			total_letter_pairs += letter_pairs
			factorial_letter = cached_factorial_mod(letter_pairs, M)
			factorial_bottom = factorial_bottom * factorial_letter % M
	factorial_top = cached_factorial_mod(total_letter_pairs, M)
	printd(factorial_top, factorial_bottom)
	factorial_bottom_inverse = fast_power(factorial_bottom, M - 2, M)
	printd('factorial_bottom_inverse', factorial_bottom_inverse)
	permutations = factorial_top * factorial_bottom_inverse % M
	printd('permutations', permutations)
	if single_letters > 0:
		permutations = permutations * single_letters % M
	printd('permutations', permutations)
	return permutations
s = input()
initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


import math
import os
import random
import re
import sys

def initialize_fact(fact, n):
	f = 1
	for i in range(1, n + 1):
		f *= i
		fact.append(f)

def initialize(s):
	a = ord('a')
	char_freq = len(s) * [26 * [0]]
	char_freq[0][ord(s[0]) - a] = 1
	for i in range(1, len(s)):
		char_freq[i] = char_freq[i - 1].copy()
		char_freq[i][ord(s[i]) - a] += 1
	return char_freq

def counts_int(l, r):
	(l, r) = (l - 1, r - 1)
	if r >= len(s):
		print('Error count index', len(s), r)
	if l == 0:
		return freq[r]
	else:
		return [freq[r][i] - freq[l - 1][i] for i in range(26)]

def modularInverse(n, p, a=[]):
	if a == []:
		a = [int(c) for c in bin(p - 2)[-1:1:-1]]
	k = len(a) * [0]
	k[0] = n % p
	for i in range(1, len(a)):
		k[i] = k[i - 1] ** 2 % p
	prod = 1
	for i in range(len(a)):
		if a[i] > 0:
			prod = prod * a[i] * k[i] % p
	return prod % p

def answerQuery(l, r):
	counts = counts_int(l, r)
	odds = sum([1 for c in counts if c % 2 == 1])
	base = [c // 2 for c in counts if c // 2 > 0]
	L = sum(base)
	assert L <= 50000
	F = fact[L]
	for b in base:
		F = F * fact_inv_mod[b] % p
	if odds == 0:
		return F % 1000000007
	else:
		return odds * F % 1000000007
s = input()
p = 10 ** 9 + 7
p2_bin = [int(c) for c in bin(p - 2)[-1:1:-1]]
fact = 50001 * [1]
for i in range(1, 50001):
	fact[i] = i * fact[i - 1] % p
fact_inv_mod = 500001 * [1]
for i in range(1, 50001):
	fact_inv_mod[i] = modularInverse(fact[i], p, p2_bin)
freq = initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


import math
import os
import random
import re
import sys
P = 10 ** 9 + 7
histograms = []
factorials = []
inv_factorials = []

def inv(x, p):
	sprev = 1
	s = 0
	(q, r) = divmod(x, p)
	while r > 0:
		snext = sprev - q * s
		sprev = s
		s = snext
		x = p
		p = r
		(q, r) = divmod(x, p)
	return s

def initialize(s):
	n = len(s)
	for i in range(1 + n):
		if i <= 1:
			factorials.append(1)
			inv_factorials.append(1)
		else:
			f = factorials[i - 1] * i % P
			factorials.append(f)
			invi = inv(i, P)
			inv_factorials.append(inv_factorials[i - 1] * invi % P)
			assert factorials[i] * inv_factorials[i] % P == 1
	histogram = [0] * 26
	for c in s:
		histograms.append(histogram.copy())
		histogram[ord(c) - ord('a')] += 1
	histograms.append(histogram)

def answerQuery(l, r):
	diff = []
	for (i, j) in zip(histograms[l - 1], histograms[r]):
		diff.append(j - i)
	pairs = []
	for i in range(len(diff)):
		count = diff[i]
		pairs.append(count // 2)
		diff[i] = count % 2
	denom = 1
	for p in pairs:
		denom = denom * inv_factorials[p] % P
	if sum(pairs) == 0:
		num = sum(diff)
	else:
		num = factorials[sum(pairs)] * max(1, sum(diff))
	return num * denom % P
s = input()
initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


import math
import os
import random
import re
import sys
from collections import defaultdict
from copy import copy

def find_inv(n, p):
	if n in inv_dict:
		return inv_dict[n]
	else:
		inv_dict[n] = find_inv(p % n, p) * (p - p // n) % p
		return find_inv(p % n, p) * (p - p // n) % p

def find_fact(n, p):
	fact_list = [0] * (n + 1)
	fact_list[0] = fact_list[1] = 1
	for i in range(2, n + 1):
		fact_list[i] = fact_list[i - 1] * i % p
	return fact_list

def answerQuery(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= find_inv(fact_list[v // 2], p_large)
		total += v // 2
		res %= p_large
	return max(1, odds) * res * fact_list[total] % p_large
s = input()
N = len(s)
inv_dict = {0: 1, 1: 1}
p_large = 1000000007
fact_list = find_fact(N // 2, p_large)
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


from functools import reduce
from copy import copy
N = int(1000000000.0) + 7

def mul(a, b):
	return a * b % N

def div(a, b):
	return mul(a, pow(b, N - 2, N))

class Factorial:

	def __init__(self, n):
		self.data = [0] * n
		self.data[0] = 1
		for i in range(1, n):
			self.data[i] = mul(self.data[i - 1], i)

	def __call__(self, n):
		try:
			return self.data[n]
		except IndexError:
			print('Factorial data not extended far enough!!!\narg: {}, n: {}'.format(n, len(self.data)))
			raise
ORDA = ord('a')

def construct_cumulative_letters(a):
	z = [[0] * 26 for _ in range(len(a))]
	z[0][ord(a[0]) - ORDA] = 1
	for i in range(1, len(a)):
		for j in range(26):
			z[i][j] = z[i - 1][j]
		z[i][ord(a[i]) - ORDA] += 1
	return z

def letters(z, l, r):
	u = copy(z[r])
	if l != 0:
		for j in range(26):
			u[j] -= z[l - 1][j]
	return u

def max_palindrome_characteristics(letters):
	one_side_letters = 0
	matching_sets = []
	central_letters = 0
	for x in letters:
		to_add = x // 2
		one_side_letters += to_add
		if to_add > 1:
			matching_sets.append(to_add)
		if x % 2:
			central_letters += 1
	return (one_side_letters, central_letters, matching_sets)

def number_arrangements(f, n, central_letters, matching_sets):
	denom = reduce(mul, map(f, matching_sets), 1)
	num = f(n)
	if central_letters > 1:
		num = mul(num, central_letters)
	return div(num, denom)
a = input()
z = construct_cumulative_letters(a)
f = Factorial(1 + len(a) // 2)
q = int(input())
for _ in range(q):
	(l, r) = (int(x) for x in input().split())
	print(number_arrangements(f, *max_palindrome_characteristics(letters(z, l - 1, r - 1))))


import math
import os
import random
import re
import sys
from collections import Counter
from itertools import permutations
from math import factorial

def initialize(s):
	return s
rl = []
fact = []
factinv = []

def result_list(s):
	rl.append(Counter(initialize(s[:1])))
	for i in range(2, len(s) + 1):
		rl.append(rl[i - 2] + Counter(initialize(s[i - 1:i])))

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	return p if y % 2 == 0 else x * p % m

def mod_inverse(a, m=10 ** 9 + 7):
	return power(a, m - 2, m)

def mod_factorial(n, m=10 ** 9 + 7):
	fact.append(1)
	if n == 0:
		return 1
	f = 1
	for i in range(1, n + 1):
		f = f * i % m
		fact.append(f)
	return f

def factor():
	for i in range(0, rl[-1].most_common(1)[0][1] // 2 + 1):
		factinv.append(mod_inverse(fact[i]))

def answerQuery(l, r):
	m = 10 ** 9 + 7
	if l != 1:
		freq = rl[r - 1] - rl[l - 2]
	else:
		freq = rl[r - 1]
	pairs = 0
	middle = 0
	divider = 1
	for i in freq.values():
		pairs += i // 2
		divider = divider * factinv[i // 2] % m
		if i % 2 != 0:
			middle += 1
	pairs_mod = fact[pairs]
	if middle == 0:
		return pairs_mod * divider % m
	else:
		return pairs_mod * middle % m * divider % m
s = input()
initialize(s)
result_list(s)
mod_factorial(50000)
factor()
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


import math
import os
import random
import re
import sys

def modmult(a, b):
	return a * b % 1000000007

def fastpow(a, n):
	if n == 1:
		return a % 1000000007
	if n == 0:
		return 1
	x = fastpow(a, n // 2)
	x = modmult(x, x)
	if n % 2 == 0:
		return x
	else:
		return modmult(a, x)

def answerQuery(frequencies, l, r):
	if l == 1:
		values = frequencies[r - 1]
	else:
		values = []
		for i in range(26):
			values.append(frequencies[r - 1][i] - frequencies[l - 2][i])
	singleletter = 0
	doubleletter = 0
	tmf = 1
	for value in values:
		doubleletter += value // 2
		singleletter += value % 2
		tmf = modmult(tmf, modinvfact[value // 2])
	combinations = modmult(fact[doubleletter], tmf)
	if singleletter:
		return combinations * singleletter % 1000000007
	else:
		return combinations
s = input()
alphabets = 'abcdefghijklmnopqrstuvwxyz'
frequencies = []
a = [0] * 26
for char in s:
	a[alphabets.find(char)] += 1
	b = a[:]
	frequencies.append(b)
fact = [1]
for i in range(1, len(s) // 2 + 1):
	fact.append(modmult(fact[-1], i))
modinvfact = []
for num in fact:
	modinvfact.append(fastpow(num, 1000000005))
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(frequencies, l, r)
	print(result)


from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


import math
import os
import random
import re
import sys

class initialize(object):

	def __init__(self, s):
		self.s = s
		self.sSet = 'abcdefghijklmnopqrstuvwxyz'
		self.start()

	def fastExpMod(self, b, e, m):
		result = 1
		while e != 0:
			if e & 1 == 1:
				result = result * b % m
			e >>= 1
			b = b * b % m
		return result

	def start(self):
		f = {i: {0: 0} for i in self.sSet}
		ff = {0: 1, 1: 1}
		fff = {0: 1, 1: 1}
		for (i, j) in enumerate(self.s):
			for m in self.sSet:
				if j == m:
					f[m][i + 1] = f[m][i] + 1
				else:
					f[m][i + 1] = f[m][i]
		for i in range(2, len(self.s) // 2 + 1):
			ff[i] = ff[i - 1] * self.fastExpMod(i, 10 ** 9 + 5, 10 ** 9 + 7) % (10 ** 9 + 7)
			fff[i] = fff[i - 1] * i % (10 ** 9 + 7)
		self.f = f
		self.ff = ff
		self.fff = fff

	def answerQuery(self, l, r):
		sall = 0
		s0 = 1
		s1 = 0
		for i in self.sSet:
			j = self.f[i][r] - self.f[i][l - 1]
			s1 += j % 2
			num = j // 2
			sall += num
			s0 *= self.ff[num]
		s1 = max(1, s1)
		return self.fff[sall] * s0 * s1 % (10 ** 9 + 7)
s = input()
mp = initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = mp.answerQuery(l, r)
	print(result)


from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


import math
import os
import random
import re
import sys
import copy
sumchars = []
MOD = 1000000007
factorials = [1] * 100001
inverses = [1] * 100001

def initialize(s):
	sumchars.append([0] * 26)
	sumchars[0][ord(s[0]) - ord('a')] += 1
	for i in range(1, len(s)):
		toAdd = copy.deepcopy(sumchars[i - 1])
		toAdd[ord(s[i]) - ord('a')] += 1
		sumchars.append(toAdd)
	for i in range(2, len(factorials)):
		factorials[i] = i * factorials[i - 1] % MOD
		inverses[i] = pow(factorials[i], MOD - 2, MOD)

def listSubtract(a, b):
	result = [0] * len(a)
	for i in range(len(a)):
		result[i] = a[i] - b[i]
	return result

def answerQuery(l, r):
	l -= 1
	r -= 1
	charCounts = sumchars[r]
	if l > 0:
		charCounts = listSubtract(sumchars[r], sumchars[l - 1])
	divisionCounts = [x // 2 for x in charCounts]
	result = factorials[sum(divisionCounts)]
	for i in divisionCounts:
		if i > 1:
			result = result * inverses[i] % MOD
	moduloCounts = [x % 2 for x in charCounts]
	result = result * max(1, sum(moduloCounts)) % MOD
	return result
s = input()
initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(l, r)
	print(result)


import math
import os
import random
import re
import sys
import time

def initialize(s):
	global minv_arr, facmod, g_count
	numAlpha = ord('z') - ord('a') + 1
	ls = len(s)
	g_count = [0] * (ls + 1)
	for i in range(ls + 1):
		g_count[i] = [0] * numAlpha
	for i in range(1, ls + 1):
		for j in range(numAlpha):
			g_count[i][j] = g_count[i - 1][j]
		g_count[i][ord(s[i - 1]) - 97] += 1
	maxNum = 0
	maxNum1 = 0
	for i in g_count[-1]:
		if i > maxNum:
			maxNum = i
	minv_arr = [0] * (maxNum // 2 + 1 + 1)
	minv_arr[0] = minv_arr[1] = 1
	m = 1000000007
	for i in range(2, maxNum // 2 + 1 + 1):
		minv_arr[i] = modInverse(i, m) * minv_arr[i - 1] % m
	facmod = [0] * 50001
	facmod[0] = 1
	facmod[1] = 1
	for i in range(2, 50001):
		facmod[i] = facmod[i - 1] * i % m % m
	return 1

def modFact(n, d, p):
	if n >= p:
		return 0
	result = 1
	for i in range(d, n + 1):
		result = result * i % p
	return result

def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		print("Inverse doesn't exist")
	else:
		return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def modularInverse(n, prime):
	dp = [0] * (n + 1)
	dp[0] = dp[1] = 1
	for i in range(2, n + 1):
		dp[i] = dp[prime % i] * (prime - prime // i) % prime
	return dp[n]

def modInverseFac(n, p):
	res = 1
	for i in range(1, n + 1):
		res = res * modInverse(i, p) % p
	return res

def modInverseMul(arrFac, p):
	res = 1
	for i in arrFac:
		for j in range(1, i + 1):
			res = res * minv_arr[j] % p
	return res

def answerQuery(s, l, r):
	start_time = time.time()
	count = [0] * (ord('z') - ord('a') + 1)
	global dp
	for i in range(len(count)):
		count[i] = g_count[r][i] - g_count[l - 1][i]
	maxLen = 0
	mark = 0
	count_odd = 0
	count_cinstr = []
	for c in count:
		if c > 0 and c % 2 == 0:
			maxLen += c
			count_cinstr.append(c // 2)
		elif c % 2 == 1:
			mark = 1
			maxLen += c - 1
			if c > 1:
				count_cinstr.append((c - 1) // 2)
			count_odd += 1
	half_max = maxLen // 2
	if mark == 1:
		maxLen += 1
	m = 1000000007
	tmp = 1
	largest = 0
	ind_large = -1
	b = 1
	a = facmod[half_max]
	for i in count_cinstr:
		b = b * minv_arr[i] % m
	total = a * b % m
	if count_odd > 0:
		total = total % m * count_odd % m
	return total % m
s = input()
initialize(s)
q = int(input())
for q_itr in range(q):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	result = answerQuery(s, l, r)
	print(result)


import math
import os
import random
import re
import sys
from collections import defaultdict
from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


import math
import os
import random
import re
import sys
from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


(W, F, G, X, M) = (input(), [1], [1], [[0] * 26], 10 ** 9 + 7)
for i in range(1, len(W) + 1):
	F.append(i * F[i - 1] % M)
	G.append(pow(F[i], M - 2, M))
	L = list(X[i - 1])
	L[ord(W[i - 1]) - 97] += 1
	X.append(L)
for _ in range(int(input())):
	(L, R) = map(int, input().split())
	(A, B, C) = (0, 1, 0)
	for i in range(26):
		x = X[R][i] - X[L - 1][i]
		if x:
			(A, B, C) = (A + x // 2, B * G[x // 2] % M, C + x % 2)
	print(F[A] % M * B * max(1, C) % M)


from collections import defaultdict
from copy import copy
mod = 1000000007
max_ele = 50000
fact = dict()
ifact = dict()
register = dict()
(fact[0], fact[1]) = (1, 1)
for i in range(2, max_ele + 1, 1):
	fact[i] = fact[i - 1] * i % mod
ifact[max_ele] = pow(fact[max_ele], mod - 2, mod)
for i in range(max_ele, 0, -1):
	ifact[i - 1] = ifact[i] * i % mod

def counter(s, l, r):
	single = 0
	non_single = []
	for letter in occurance_of_letter[r]:
		j = occurance_of_letter[r][letter] - occurance_of_letter[l - 1][letter]
		if j == 1:
			single += 1
		elif j % 2 == 0:
			non_single.append(j // 2)
		else:
			non_single.append(j // 2)
			single += 1
	y = fact[sum(non_single)]
	for i in non_single:
		if i == 1:
			continue
		y = y * ifact[i] % mod
	if single == 0:
		ans = y % mod
	else:
		ans = y * single % mod
	return int(ans)
s = input()
count = int(input())
occurance_of_letter = [defaultdict(int)]
for ch in s:
	newd = copy(occurance_of_letter[-1])
	newd[ch] += 1
	occurance_of_letter.append(newd)
for i in range(count):
	get_sting = input().split()
	l = int(get_sting[0])
	r = int(get_sting[1])
	if (l, r) in register:
		print(register[l, r])
	else:
		collect = counter(s, l, r)
		register[l, r] = collect
		print(collect)


mod = 10 ** 9 + 7

def factorials(n):
	res = [0] * (n + 1)
	prev = 1
	for i in range(1, n + 1):
		prev = prev * i % mod
		res[i] = prev
	return res

def init(s):
	(cnt, data) = ([0] * 26, [[]] * (len(s) + 1))
	data[0] = list(cnt)
	for (i, c) in enumerate(s):
		cnt[ord(c) - 97] += 1
		data[i + 1] = list(cnt)
	return (data, factorials(sum(cnt)))

def modInv(a, mod):

	def egcd(a, b):
		(x, y, u, v) = (0, 1, 1, 0)
		while a != 0:
			(q, r) = (b // a, b % a)
			(m, n) = (x - u * q, y - v * q)
			(b, a, x, y, u, v) = (a, r, u, v, m, n)
		GCD = b
		return (GCD, x, y)
	(_, x, y) = egcd(a, mod)
	return x % mod

def calculate_palindromes(parts, middle, fact):
	if len(parts) == 0:
		return middle
	(A, B) = (fact[sum(parts)], 1)
	for v in parts:
		B = B * fact[v] % mod
	res = A * modInv(B, mod) % mod
	if middle:
		return middle * res % mod
	return res

def find(data, fact, s, e):
	(middle, parts) = (0, [])
	for (v_s, v_e) in zip(data[s - 1], data[e]):
		tmp = v_e - v_s
		if tmp > 0:
			middle += tmp % 2
		if tmp // 2:
			parts.append(tmp // 2)
	return calculate_palindromes(parts, middle, fact)
(data, fact) = init(input())
res = []
for _ in range(int(input())):
	(s, e) = tuple(map(int, input().split()))
	res.append(find(data, fact, s, e))
print('\n'.join(map(str, res)))


from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


s = input()
from math import factorial
mod = 10 ** 9 + 7
F = [1]
for i in range(1, 10 ** 5 + 2):
	F.append(F[-1] * i % mod)
A = {'a': [0], 'b': [0], 'c': [0], 'd': [0], 'e': [0], 'f': [0], 'g': [0], 'h': [0], 'i': [0], 'j': [0], 'k': [0], 'l': [0], 'm': [0], 'n': [0], 'o': [0], 'p': [0], 'q': [0], 'r': [0], 's': [0], 't': [0], 'u': [0], 'v': [0], 'w': [0], 'x': [0], 'y': [0], 'z': [0]}
for c in s:
	for a in A:
		A[a].append(A[a][-1])
	A[c][-1] += 1
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	even = []
	numodd = 0
	for a in A:
		count = A[a][r] - A[a][l - 1]
		if count <= 0:
			continue
		if count % 2:
			numodd += 1
			even.append(count - 1)
		else:
			even.append(count)
	S = 0
	div = 1
	for e in even:
		e //= 2
		S += e
		div = div * F[e] % mod
	res = F[S] % mod * pow(div, mod - 2, mod)
	if numodd:
		res *= numodd
	print(res % mod)


from collections import defaultdict
from copy import copy
M = int(1000000000.0) + 7
fact = [1]
for i in range(1, int(100000.0) + 10):
	fact.append(fact[-1] * i % M)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
memo = {}

def modinv(a, m):
	if a in memo:
		return memo[a]
	while a < 0:
		a += m
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('Modular inverse does not exist')
	else:
		memo[a] = x % m
		return x % m
s = input().strip()
occ = [defaultdict(int)]
for ch in s:
	newd = copy(occ[-1])
	newd[ch] += 1
	occ.append(newd)

def query(l, r):
	d = defaultdict(int)
	for ch in occ[r]:
		d[ch] += occ[r][ch]
	for ch in occ[l - 1]:
		d[ch] -= occ[l - 1][ch]
	odds = 0
	for (k, v) in copy(d).items():
		if v & 1:
			odds += 1
		d[k] = v - (v & 1)
	res = 1
	total = 0
	for (k, v) in d.items():
		res *= modinv(fact[v // 2], M)
		total += v // 2
		res %= M
	return max(1, odds) * res * fact[total] % M
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(query(l, r))


import sys, math
MOD = 10 ** 9 + 7
fact = [1]
cur = 1
for i in range(1, 6 * 10 ** 4):
	cur *= i
	cur %= MOD
	fact.append(cur)
alpha = 'abcdefghijklmnopqrstuvwxyz'
dp = [0]
dp2 = [[0] * 26]

def bitm(c):
	return 1 << alpha.find(c)

def initialize(s):
	cur = 0
	for c in s:
		tmp = [i for i in dp2[-1]]
		tmp[alpha.find(c)] += 1
		cur ^= bitm(c)
		dp.append(cur)
		dp2.append(tmp)

def modInv(x, pow=MOD - 2):
	if pow <= 3:
		return x ** pow % MOD
	else:
		tmp = modInv(x, pow // 2)
		tmp *= tmp
		tmp %= MOD
		if pow % 2 == 0:
			return tmp
		else:
			return tmp * x % MOD
mi = [modInv(fact[x]) for x in range(6 * 10 ** 4)]

def answerQuery(l, r):
	tmp = dp[l - 1] ^ dp[r]
	tmp2 = [(dp2[r][i] - dp2[l - 1][i]) // 2 for i in range(26)]
	possLetters = 0
	for c in range(26):
		if tmp & 1 << c:
			possLetters += 1
	middle = max(possLetters, 1)
	others = (r - l + 1 - possLetters) // 2
	ans = fact[others] * middle % MOD
	for i in tmp2:
		if i > 0:
			ans *= mi[i]
			ans %= MOD
	return ans
s = input().strip()
initialize(s)
q = int(input().strip())
for a0 in range(q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	result = answerQuery(l, r)
	print(result % MOD)