Vaibhav Sir and Saikat Sir are sending encrypted messages to each other. The message is encrypted by changing each letter to its previous or next letter ('A' can be changed to 'Z' or 'B').

Since a large number of encryptions are possible for a given string, they decide that-

1. 2 consecutive characters in the encrypted string should not be the same.
2. The characters at some positions will always be replaced by the next character (called Fixed Positions).

Input

The input starts with T (number of test cases) followed by 2 lines for each test case.
First line consists of the input string to be encrypted  of maximum length 5000 containing characters 'A' to 'Z'.
Second line consists of an integer N, followed by N space separated integers A(i) in increasing order.
N = number of fixed positions.
A(i) = ith fixed position.

Output

Output contains T lines, the ith line containing the number of possible encryptions for the ith test case modulo 1000000007.

Constraints

T<=25
1<=length of string(L)<=5000
0<=N0<=A(i)

Example

Input:
2
CODER
0
ABCDEF
2 0 5

Output:
32
16