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 = S₀S₁…S_N-1 be a string of length N containing only the lowercase letters (a-z).

Hash(S) = ∑ B^N-i-1 * D(S_i) % 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 10⁹ + 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 10⁹ + 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