King Sam's kingdom has a large number of cities. All the cities are linearly placed and have teleportation chambers installed in each of them for ease of travel. Each teleportation chamber is assigned an alphabet. King Sam is in the first city and his queen is in the last city. So, he wishes to find out the number of paths he has, to visit his queen in the last city.
- King Sam can either go from the ith city to the (i+1)th city.
- Or King Sam can teleport to the jth city where j > i and s[j] = (s[i]+k)%26 where s[i] is the alphabet assigned to the teleportation chamber in ith city.
The value of 'k' keeps changing. So you need to find, for different values of 'k' in 'Q' situations, the number of paths he has to reach his queen.
Input Format:
The First line will contain a string containing only lowercase English alphabets which are assigned to the teleportation chambers in each city in order. The Second line will contain the number of Queries Q. After that Q lines will be present and each line will contain one integer which is the value of k.
Output Format:
You need to print Q lines of output where ith line contain the answer for ith query.
Constraints:
1 <= Length Of String or Number of cities <= 10^6
1 <= Q <= 10^6
0 <= k <= 10^9
Note:
As the answer can be very large print it modulo 10^9+7.
Now in the first query when k = 0 from the second constraint King Sam can go from a city which contains character 'a' to any position which also contains the character 'a' . So the total number of distinct paths are 8.
For the rest of the queries the value of k is greater than 0 which means he can only use the first constraint to move so the number of distinct paths are 1.
