Yet Another XYZ Problem

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⁹+7.

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.

For each testcase, print one integer indicating the answer.

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

1
0
4

2015 Multi-University Training Contest 4