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