STRDIST2 - String distance

no tags 

Prof. XYZ is an expert in sequence analysis. One such problem he works on is bar-coding DNA sequences. The problem at hand is, given two DNA sequences, find a way to compute their similarity efficiently. Formally a DNA sequence is a string (S) of length N where each character is from a set of symbols derived from a vocabulary ∑. We define the m-perturbed set of a string S to be  Δ (S, m) which contains the set of all strings S' obtained by changing at most m characters of S with m <= N. In other words, Δ (S, m) is the set of all strings S' such that the hamming distance between S and S' (defined by H(S, S')) is at most m. 

Prof. XYZ defines an order (m1, m2) similarity between two N-length strings S1 and S2 to be the number of strings in the intersection of Δ(S1, m1) and Δ(S2, m2). It is easy to see that the number of strings in this intersection only depends on the hamming distance between S1 and S2 (rather than the entire original strings S1 and S2). In other words |Δ(S1, m1) ∩ Δ(S2, m2)| is only a function of N, the hamming distance H(S1, S2), m1, m2 and the alphabet size |∑|. Your objective is to write a program that counts the size of this intersection given  N, m1, m2, H(S1, S2) and |∑|. Since the answer can be very large, output the answer modulo 1000000007.

Input

The first line of the input contains the number of test cases T (at most 50). Each test case consists of 5 integers in order:

  1. N : The length of each of the two strings. 1 <= N <= 1000
  2. m1 : The allowed number of changes in the first string. 0 <= m1 <= min(100, N/2)
  3. m2 : The allowed number of changes in the second string. 0 <= m2 <= min(100, N/2)
  4. H(S1, S2): The hamming distance between the two strings. 0 <= H <= min(100, N/2)
  5. |∑| : The size of the vocabulary. 2 <= |∑| <= 1000000

Output

For each test-case output the required number of strings in the intersection modulo 1000000007 in a separate line.

Example

Input:
3
6 1 2 2 2
10 2 2 3 5
20 3 4 5 7

Output:
3
24
1925

Explanation

The length of each string is 6. We are allowed to perturb at most one element from the first string and at most two elements from the second. Since their hamming distance needs to be two, let S1 = 000000 be the first string and S2 = 000011 be the second. The set Δ(S1, 1) is  {000000, 000001, 000010, 000100, 001000, 010000, 100000}. Without enumerating Δ(S2, 2), we can see that the only set of strings in Δ(S1, 1) that can be obtained by perturbing at most two elements in S2 are {000000, 000001, 000010}. Thus |Δ(S1, m1) ∩ Δ(S2, m2)| = 3.



Added by:Balakrishnan
Date:2011-04-26
Time limit:2.846s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:The problem was stated in a technical talk.