Problem H
Strings
Input: Standard Input

Output: Standard Output

Given 3 strings of only lowercase letter you have to count the number of ways you can construct the third string by combining two subsequences from the first two strings.

After deleting 0 or more characters from a string we can get its subsequence. For example “a”, “b”, “c”, “ab”, “ac”, “bc” and “abc” all the strings are the subsequences of “abc”. A subsequence may also be empty.

Now suppose 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” and “deabc”.

Input

The first line of the input contains a single integer T (0<T<271) indicating the number of test cases.  Each test case contains 3 strings containing only lowercase characters. The lengths of the strings are between 1 and 60.

Output

For each test case output a single integer denoting the number of ways you can construct the third string from the first two string by the above way. The result may be very large. You should output the result%10007.

Sample Input                             Output for Sample Input

Problemsetter: Abdullah-al-Mahmud

Special Thanks: Md. Kamruzzaman

題目描述：

不改變 A, B兩個字串的順序，抽出來組合成 C，問方法數若干？

題目解法：

狀態一定是 dp[lc][la][lb], 表示成當前 substringC, substringA, substringB

然後嘗試將 substringC 的 tail 去匹配 substringA, substringB 的其中一個字串，

接著去掉匹配的字串之後，繼續求解。

整體來說最慘到 O(n^4)，但如果字符種類差異很大速度會比較快，有機會達到 O(n^3)，甚至更小。