Beautiful Flowers - Hoa dep (But Wait, There Are Some Changes Version)


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

Tuan's house has a row of \(N\) single-colored flower pots. Looking at the flowers every day, Tuan noticed that it looks very beautiful if the pots of the same color are placed entirely on the same side (left half or right half) of the row.

The sequence of pot colors is represented as a string \(S\) of even length \(N\), where each color is a lowercase or uppercase Latin letter, indexed from \(1\) to \(N\). A string \(S\) is called a beautiful string if every group of identical characters lies entirely within the left half or entirely within the right half of \(S\). For example, the strings abcd and AbaB are beautiful strings, while aaaa or Bbba are not.

However, Tuan is not someone whose flaw is excessive perfectionism - he appreciates a bit of artistic variation. So he calls a row of pots artistically beautiful if it is a beautiful string, or if at most one chosen pot color is allowed to appear on both sides.

Tuan wants to know: for two given colors that must lie on the same side, how many arrangements of the pots are artistically beautiful?

To put it briefly, you must answer \(Q\) queries. Each query consists of three Latin characters \(x, y, z\). Output the number of strings \(T\) satisfying:

  • \(T\) is a permutation of \(S\);
  • \(T\) is an artistically beautiful string;
  • Characters \(x\) and \(y\) must lie on the same side (either left or right) in string \(T\);
  • Character \(z\) is the one allowed to appear on both sides.

Input

  • The first line contains the string \(S\) (\(|S| = N = 2k;\ k \le \frac{5\times10^4}{2}\));
  • The second line contains a positive integer \(Q\) (\(Q \le 10^3\));
  • Each of the next \(Q\) lines contains three Latin characters \(x, y, z\) (\(z \neq x;\ z \neq y\)).

Output

\(Q\) lines, each being the answer to the corresponding query, modulo \((10^9+7)\).

Constraints

  • Subtask 1 (20%): \(Q = 1;\ 0 < k \le \frac{10^3}{2}\).
  • Subtask 2 (80%): No additional constraints.

Examples

Example 1

input

AbdbCC
2
A d b
b C A

output

36
0

Explanation

For query 1, some of the valid strings are: AdbbCC, AbdbCC, bAdCbC.


Comments

There are no comments at the moment.