## AHASH2 - Anti Hash II

Given a base B and a modulo M, the polynomial hash of a string S consisting of only lowercase letters is defined as below.

Let S = S0S1…SN-1 be a string of length N containing only the lowercase letters (a-z).

Hash(S) = ∑ BN-i-1 * D(Si) % M

D(S) = Lexicographical position of character S among the letters a-z, indexed from 0. D(a) = 0, D(b) = 1, … , D(z) = 25.

In other words, first the letters of the string are replaced by numbers (equivalent to their position). This is then considered to be a number in base B, and the value of this number in base 10 modulo M is called the polynomial hash of the string.

Calculating the hash of a string using the above method seems easy enough. What about the opposite? You are given a base B, a modulo M, a positive integer N, and a hash value H. Calculate how many strings are there such that their hash is equal to H, consisting of only lowercase letters and their length not exceeding N. Since the answer can be rather huge, output it modulo 109 + 7 (1000000007).

### Input

The first line contains an integer T, denoting the number of test cases. Each test case starts with four integers B, M, N, Q. The numbers B, M, N denotes the base, modulus and the maximum length of any string as stated above. The number Q indicates the number of queries. Each of the next Q lines contain a single integer, denoting H, the required hash value.

### Constraints

• 1 ≤ T ≤ 150
• 26 ≤ B ≤ 30000
• 1 ≤ M, N ≤ 30000
• 1 ≤ Q ≤ 300
• 0 ≤ H < M
• For 95% of the test cases, B, M, N ≤ 300
• ### Output

For each case, first output a line of the format Case X:, where X is the case number, starting from 1. And then, for each query, output the number of different strings with the given hash value modulo 109 + 7 (1000000007) in a single line.

Print a blank line after every test case.

### Sample Input

```3
26 97 2 3
0
1
96
147 147 147 3
0
10
100
100 110 120 1
35
```

### Sample Output

```Case 1:
8
8
6

Case 2:
944164777
944164777
0

Case 3:
110169522

```

### Challenge

You might also enjoy:

Anti Hash

The Revenge Of Anti Hash

 Added by: sgtlaugh Date: 2020-06-09 Time limit: 10s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All Resource: Own Problem, Used in 2017-2018 Asia Yangon Regional Contest