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-
- 2 consecutive characters in the encrypted string should not be the same.
- 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<=NExample
Input:
2
CODER
0
ABCDEF
2 0 5
Output:
32
16
hide comments
anonymous:
2023-02-15 23:35:48
There are test cases containing characters outside 'A' .. 'Z' range (my AC program assumed that prev / next is c - 1 / c + 1 for those). |
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 |