Given three strings A, B and C you have to count the number of ways you can construct C by combining two subsequences from A and B.
After deleting 0 or more characters from a string we can get its subsequence. For example "a", "b", "c", "ab", "ac", "bc", "abc", "" are the subsequences of "abc".
Now, suppose that there are two subsequences "abc" and "de". By combining them you can get the following strings: "abcde", "abdce", "abdec", "adbce", "adbec", "adebc", "dabce", "dabec", "daebc", "deabc".Reduce ca
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing three strings A, B and C. The strings will contains only lowercase letters and the lengths of the strings are between 1 and 100 (inclusive).
Output
For each case, print the case number and the number of ways you can construct C from the first two strings: A and B by the above way. The result can be large, so print the result modulo 1000000007 (109 + 7).
Sample
| Sample Input | Sample Output |
|---|---|
2 abc abc abc abbcd bccde abcde | Case 1: 8 Case 2: 18 |