Destroy the Colony
Contest: CodeCraft-19 and Codeforces Round 537 (Div. 2)
Difficulty rating: 2600
Tags: combinatorics, dp, math

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.

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
abba
2
1 4
1 2

Example output:
2
0

Example input:
AAaa
2
1 2
1 3

Example output:
2
0

Editorial:
The question reduces to the following. Given a string s with lowercase and uppercase characters,a good string is one which can be generated by reshuffling characters, such that all occurences of a particular alphabet are in the same half. ( (1 to n/2) or (n/2+1 to n)) and this condition is true for all alphabets. Now given a pair $$$i$$$ and $$$j$$$, you want to find the number of good strings such that all the occurences of $$$s[i]$$$ and $$$s[j]$$$ in the string are also in the same half in the string.
Lets first try to find the number of good strings. $$$k$$$ = total number of alphabets.
Store the frequencies of the alphabets as their order does not matter, and let them be $$$c1,c2,c3..ck$$$ Now if we can select indices $$$i_1, i_2, \ldots, i_p$$$ such that $$$ci_1 + ci_2 + \ldots, ci_p$$$ = n/2 then we can arrange those alphabets in the first half, and the remaining in the second half. Total ways for arranging in first half = $$$(n/2!)/(ci1!* ci2!* ci3!.. cip!)$$$
Similarly total ways for arranging in 2nd half = $$$(n/2!)/$$$(product of factorials of remaining frequencies.)
Thus total ways = $$$((n/2!)*(n/2!))/$$$(product of factorials of frequencies of all alphabets) $$$= W$$$(say) Thus notice that, for all combinations of frequencies adding upto $$$n/2$$$, the number of ways comes out to be constant.
Hence now the total number of good strings $$$= W*$$$ (number of combinations of frequencies adding to $$$n/2$$$)
The part for the number of combinations adding upto $$$n/2$$$ can be computed using standard knapsack dp.
Now let's try to solve for the condition that all occurrences of $$$s[i]$$$ and $$$s[j]$$$, should all also be in the same half, apart from the condition of the string being a good string.
This basically means now we want to select alphabet frequencies adding upto $$$n/2$$$ from the remaining frequencies ( excluding the frequency of alphabet $$$s[i]$$$ and $$$s[j]$$$). One way is to use the same method we did above for all good strings.
This gives complexity O$$$(n*k)$$$ for every pair, taking a total of O$$$(n*k^3)$$$ for $$$k^2$$$ pairs.
Now using the idea of adding items to a knapsack, we can also extend it to remove items.
In short, we can use the pre-computed dp table to remove the number of ways which included the ith item, by reversing the direction of the loop and the operation ( addition becomes subtraction). Let the frequency of the element we want to remove be $$$x$$$.
dp[j] = number of ways to get sum as j using all elements.
for (int j=x;j<=n;j++)
$$$\quad$$$dp[j]-=dp[j-x];
( see the code for more details)
In this way for every pair $$$(x,y)$$$, you copy the precomputed dp into a temporary array, remove ways using characters $$$x$$$ and $$$y,$$$ and then the answer will be $$$2*dp[n/2]*W$$$ ( 2 because you can choose the first or the second half for putting the group containing $$$x$$$ and $$$y$$$). After precomputation, each query is answered in O$$$(1)$$$. Total time O$$$(2*n)$$$, for every pair and there are $$$(k*(k-1))/2$$$ pairs. Final time complexity O$$$(n*k^2)$$$