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 109+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