Destroy the Colony

题意翻译

有一个恶棍的聚居地由几个排成一排的洞穴组成，每一个洞穴恰好住着一个恶棍。 每种聚居地的分配方案可以记作一个长为**偶数**的字符串，第$i$个字符代表第$i$个洞里的恶棍的类型。 如果一个聚居地的分配方案满足对于所有类型，该类型的所有恶棍都住在它的前一半或后一半，那么钢铁侠可以摧毁这个聚居地。 钢铁侠的助手贾维斯有不同寻常的能力。他可以交换任意两个洞里的野蛮人（即交换字符串中的任意两个字符）。并且，他可以交换任意次。 现在钢铁侠会问贾维斯$q$个问题。每个问题，他会给贾维斯两个数$x$和$y$。贾维斯要告诉钢铁侠，从当前的聚居地分配方案开始，他可以用他的能力创造多少种不同的方案，使得与原来住在第$x$个洞或第$y$个洞中的恶棍类型相同的所有恶棍都被分配到聚居地的同一半，同时满足钢铁侠可以摧毁这个聚居地。 如果某一个洞里的恶棍在两种方案中类型不同，则这两种方案是不同的。 输入 第一行包含一个字符串$s$ ($2\leq |s| \leq 10^5$)，表示初始的聚居地分配方案。字符串$s$包含小写和大写英文字母，且长度为偶数。 第二行包含一个整数$q$——询问的数量。 接下来的$q$行中的第$i$行包含两个整数$x_i$和$y_i$ ($1\leq x_i, y_i \leq |s|$)——第$i$个问题中给贾维斯的两个整数。 输出 对于每个问题输出可能的分配方案数模$10^9+7$。

题目描述

There is a colony of villains with several holes aligned in a row, where each hole contains exactly one villain. Each colony arrangement can be expressed as a string of even length, where the $ i $ -th character of the string represents the type of villain in the $ i $ -th hole. Iron Man can destroy a colony only if the colony arrangement is such that all villains of a certain type either live in the first half of the colony or in the second half of the colony. His assistant Jarvis has a special power. It can swap villains of any two holes, i.e. swap any two characters in the string; he can do this operation any number of times. Now Iron Man asks Jarvis $ q $ questions. In each question, he gives Jarvis two numbers $ x $ and $ y $ . Jarvis has to tell Iron Man the number of distinct colony arrangements he can create from the original one using his powers such that all villains having the same type as those originally living in $ x $ -th hole or $ y $ -th hole live in the same half and the Iron Man can destroy that colony arrangement. Two colony arrangements are considered to be different if there exists a hole such that different types of villains are present in that hole in the arrangements.

输入输出格式

输入格式

The first line contains a string $ s $ ( $ 2 \le |s| \le 10^{5} $ ), representing the initial colony arrangement. String $ s $ can have both lowercase and uppercase English letters and its length is even. The second line contains a single integer $ q $ ( $ 1 \le q \le 10^{5} $ ) — the number of questions. The $ i $ -th of the next $ q $ lines contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i, y_i \le |s| $ , $ x_i \ne y_i $ ) — the two numbers given to the Jarvis for the $ i $ -th question.

输出格式

For each question output the number of arrangements possible modulo $ 10^9+7 $ .

输入输出样例

输入样例 #1

abba
2
1 4
1 2

输出样例 #1

2
0

输入样例 #2

AAaa
2
1 2
1 3

输出样例 #2

2
0

输入样例 #3

abcd
1
1 3

输出样例 #3

8

说明

Consider the first example. For the first question, the possible arrangements are "aabb" and "bbaa", and for the second question, index $ 1 $ contains 'a' and index $ 2 $ contains 'b' and there is no valid arrangement in which all 'a' and 'b' are in the same half.