DCEPC904 - Secret Code

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

Added by:dce coders
Date:2012-08-26
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Own Problem

hide comments
2023-02-15 23:35:48 anonymous
There are test cases containing characters outside 'A' .. 'Z' range (my AC program assumed that prev / next is c - 1 / c + 1 for those).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.