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 atmost 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 atmost 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 (atmost 50). Each testcase 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 seperate line.

Example

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


Output:
3
24
1925

Explanation (for the first test case)

The length of each string is 6. We are allowed to perturb atmost one element from the first string and atmost 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 atmost two elements in S2 are {000000,000001,000010}. Thus |Δ(S1,m1) ∩ Δ(S2,m2)| =3.