Q11081: Strings
給你三個只有小寫字母的字串，計算有幾種方法可以把前兩個字串的子序列(subsequence)合併成第三個字串。
刪除一個字串中 0 個或更多字元之後，可以得到他的子序列。例如“a”, “b”, “c”, “ab”, “ac”, “bc” 和 “abc”，都是“abc”的子序列。一個子序列也可以是空的。
假設有兩個字串“abc”和“de”，合併他們你可以得到以下字串“abcde”, “abdce”, “abdec”, “adbce”, “adbec”, “adebc”, “dabce”, “dabec”, “daebc”和“deabc”。
Input
第一行有一個數字 T 表示測資有幾組。每行都有三個只有小寫字母的字串，這些字串的長度都在 1 到 60 之間。
Output
對每組測資輸出 有幾種方法可以用上述方式將前兩個字串合併成第三個字串。答案可能會非常大，你應該輸出答案%10007。
Sample Input
Sample Output
2 abc abc abc abbcd bccde abcde
8 18
Translated by DarkKnight