D. Уничтожить поселение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поселение злодеев представляет из себя несколько логов, расположенных в линию. В каждом логове живет ровно один злодей.

Каждое поселение можно представить как строку четной длины, где $$$i$$$-й символ строки определяет тип злодея, живущего в $$$i$$$-м логове.

Железный человек может уничтожить поселение, если только все злодеи каждого типа живут либо только в первой половине поселения, либо только во второй половине.

У его помощника Джарвиса есть суперспособность. Он может поменять местами жителей любых двух логов, иным словами, поменять местами любые две буквы строки. Он может выполнить эту операцию любое число раз.

Железный человек задает Джарвису $$$q$$$ вопросов. В каждом вопросе он дает Джарвису два номера $$$x$$$ и $$$y$$$. Джарвис должен ответить, сколько различных вариантов поселения он может сделать из исходного таких, что все злодеи, тип которых совпадает с типом злодея, находящегося изначально в $$$x$$$-м или $$$y$$$-м логове, живут в одной и той же половине, и Железный человек может уничтожить это поселение.

Два варианта поселения считаются различными, если существует логово, в которых живут злодеи различного типа в этих двух вариантах.

Входные данные

Первая строка содержит строку $$$s$$$ ($$$2 \le |s| \le 10^{5}$$$), описывающую начальный вариант поселения. Строка $$$s$$$ состоит из строчных и заглавных латинских букв и имеет четную длину.

Вторая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^{5}$$$) — количество вопросов.

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le |s|$$$, $$$x_i \ne y_i$$$) — два номера, данные Джарвису в $$$i$$$-м вопросе.

Выходные данные

Для каждого вопроса выведите остаток от деления количества вариантов поселений на $$$10^9+7$$$.

Примеры
Входные данные
abba
2
1 4
1 2
Выходные данные
2
0
Входные данные
AAaa
2
1 2
1 3
Выходные данные
2
0
Входные данные
abcd
1
1 3
Выходные данные
8
Примечание

Рассмотрим первый пример. В первом вопросе возможные варианты поселения это «aabb» и «bbaa». Во втором вопросе логово $$$1$$$ содержит злодея типа «a», а логово $$$2$$$ содержит злодея типа «b», и не существует варианта поселения, где все «a» и «b» находятся в одной половине.