odd doctor 已更新

Yet Another XYZ Problem

Time Limit
1s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
100.00%(2/2)
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 109+7.

Input:

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

For each of the testcases, the first line contains four integers Cost0,Cost1,Cost2,maxCost(1Cost0,Cost1,Cost21e18,0maxCost1e18). 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:

2015 Multi-University Training Contest 4


Submit