Description:

You have two strings A and B which consist of x,y,z. Every time, you can do one of the following three operations:

1. Change all the x in A into y. This operation costs Cost0.

2. Change all the y in A into z. This operation costs Cost1.

3. Change all the z in A into x. This operation costs Cost2.

One extra restriction is that when you operate any of these operations, the string A needs to be changed. More specifically, when you operate the first operation, there should be at least one x in string A, etc. Please calculate how many different ways there are to change the string A into string B, while using not more than macCost total cost. The answer could be very large, so please print the actual answer module 10^{9}+7.

Input:

The first line of the input is a single integer T (T≤1000), indicating the number of testcases.

For each of the testcases, the first line contains four integers Cost0,Cost1,Cost2,maxCost(1≤Cost0,Cost1,Cost2≤1e18,0≤maxCost≤1e18). The second line contains the string A, and the third line contains the string B. It is guaranteed that the length of A is the same with that of B.

The size of the input file is less than 50 KB.

Output:

For each testcase, print one integer indicating the answer.

Sample Input:

3 1 1 1 0 x x 1 1 1 0 x y 1 1 1 10 x x

Sample Output:

1 0 4

Source:

Submit