Monica is the Head-chef at Javu's restaurant. Javu has N kitchen workers, numbered from 1 to N. Each kitchen worker has expertise in exactly one of the following fields:

1. VEG - denoted as V
2. NONVEG - denoted as N
3. GRILL - denoted as G
4. TOAST - denoted as T
5. SANDWICH - denoted as S
6. BURGER - denoted as B
7. PIZZA - denoted as P

You'll be given the string S₁ of length N, where i^th character defines the field of expertise of i^th worker, 1 ≤ i ≤ N.
Now, a customer's order contains 3 fields:

You'll be given a string S₂ of length 3, where j^th character defines the j^th field of the order, 1 ≤ j ≤ 3.
The first character will either be V or N. Second character will either be G or T. Third character will either be S or B or P.

According to the customer order, Monica has to form a team of workers who can prepare the order. Javu has received M orders at the moment. You have to find in how many ways can Monica prepare a team of 3 workers for each of the orders.

Note: One worker can only work in one team. See the sample test case for clarification.

Input:
First line of input contains N - number of workers.
Second line contains a string S₁ of length N, where i^th character defines the field of expertise of i^th worker, 1 ≤ i ≤ N.
Third lines contains M - number of orders.
Each of the next M lines contain an order query S₂.

Output:
For each order query, print the number of ways Monica can form a team of 3 workers who can prepare the order.
Since the answer can be very large, print it modulo 1000000007 ( 10⁹ + 7 )

Constraints:
1 ≤ N ≤ 1000000
String S₁ will be of length N and will only contain upper case character [V, N, G, T, S, B, P]
1 ≤ M ≤ 300000
String S₂ will be of length 3 and will only contain upper case character [V, N, G, T, S, B, P]