Yet Another XYZ Problem

Problem 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 \le 1000)$, indicating the number of testcases. For each of the testcases, the first line contains four integers $Cost0, Cost1, Cost2, maxCost(1 \le Cost0, Cost1, Cost2 \le 1e18, 0 \le maxCost \le 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

Author

XJZX

Source

2015 Multi-University Training Contest 4