Heisenberg and his skills

3

1 votes
Easy
Problem

As we all know, Heisenberg's real name is Walter White, and he is a complete genius when it comes to Chemistry and science. But one of the most important skills he has is, he knows his business and the trade. He knows what he is up to and what are the things that will keep his business growing.

enter image description here

He has successfully managed to keep his family in the dark and none of the members, even his brother-in-law who is a DEA agent, doesn't know about his real identity outside the house. He has synthesized the purest methamphetamine, with the 'blue' crystals. To stay away from the DEA and to grow his territory, he goes to deal with his enemies the right way. They are located somewhere in an abandoned place in the outskirts of Albuquerque.

enter image description here

To catch them, he goes to a small abandoned factory which has a box right beside the entry door. In the box, there are Q cards with a couple of numbers written on one side, but among all those cards there are only some cards with an alphabet visible on the other side. Since the factory is old, he could not see the alphabet on the rest of the cards due to the fade.

The cards he had seen were (showing the two numbers present on one side and the alphabet on the other) -

1.) 192, 2 ----> 'a'
2.) 90, 114 ----> 'f'
3.) 54, 144 ----> 'c'
4.) 200, 44 ----> 'z'

After looking closely, he observes that there is a relation between the pair of numbers and the alphabet. He deduces the pattern and assigns the alphabet to the remaining cards.

There is a string S written on the top of the factory which consists of only lowercase letters. To find out where the enemies are, he needs to solve a problem written on the window. The problem is -

For each of the characters ch from the Q cards, he needs to extract all occurrences of character ch from the string S one by one. Find out the number of possible ways to do so. Output the sum of possible ways for all the Q characters.

Example: Let us assume that the given string is 'abababcc'. And the characters are 'a' and 'b'. A is present in positions 1, 3 and 5. So possible orders are 1,3,5 1,5,3 3,1,5 3,5,1 5,3,1 and 5,1,3. So there are 6 possible ways to extract 'a' from the given string. Similarly, there are 6 possible ways for 'b'. So output will be 6+6=12.

INPUT

  • First line contains an integer T, the number of Test Cases.
  • Each test case consists of the following lines:
  • The first line denotes a string S.
  • The next line contains an integer Q, denoting the number of cards.
  • Then Q lines follows, each line contains 2 space separated integers X and Y. Denoting the 2 integers on one side of the card.

OUTPUT

  • Output the answer of each test case in a separate line. Since the answer can be large, output it modulo 109+7.

CONSTRAINTS

  • 1 ≤ T ≤ 103
  • 1 ≤ |S| ≤ 106
  • 1 ≤ T*|S| ≤ 106
  • 1 ≤ Q ≤ 26
  • All characters of the Q cards are distinct lowercase alphabets.
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?