Đếm cách trộn xâu

Cho ba xâu \(S\), \(T\), \(U\) chỉ gồm chữ cái thường. Ta muốn tạo ra xâu \(U\) bằng cách chọn một dãy con của \(S\) và một dãy con của \(T\) (dãy con nhận được bằng cách xoá đi một số ký tự, có thể không xoá) rồi trộn hai dãy con đó: các ký tự của mỗi dãy con giữ nguyên thứ tự tương đối nhưng có thể xen kẽ tuỳ ý với dãy kia.

Chính xác hơn, một cách xây dựng là việc chọn:

• một tập vị trí của \(U\) được lấy từ \(S\) (các vị trí còn lại của \(U\) lấy từ \(T\));
• một bộ chỉ số tăng dần trong \(S\), mỗi chỉ số ứng với một vị trí đã chọn ở trên sao cho ký tự trùng khớp;
• tương tự một bộ chỉ số tăng dần trong \(T\) cho các vị trí còn lại.

Hai cách xây dựng khác nhau nếu tập vị trí của \(U\) lấy từ \(S\) khác nhau, hoặc các chỉ số được chọn trong \(S\) hay \(T\) khác nhau.

Hãy đếm số cách xây dựng, in ra phần dư khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa số nguyên \(t\) là số bộ test.
• Mỗi bộ test gồm một dòng chứa ba xâu \(S\), \(T\), \(U\) cách nhau bởi dấu cách.

Output

Với mỗi bộ test in ra một dòng chứa đáp án theo modulo \(10^9+7\).

Constraints

• \(1 \le t \le 20\)
• Độ dài mỗi xâu từ \(1\) đến \(60\), chỉ gồm chữ cái a–z.

Sample Input

3
ab ba abba
aaa aa aaa
abab abb babb

Sample Output

2
28
19

Explanation

Với bộ đầu tiên, \(U\) = abba dài \(4\) nên phải dùng cả ab và ba. Có hai cách: lấy các vị trí \(\{1,2\}\) của \(U\) từ \(S\) (còn \(\{3,4\}\) từ \(T\)), hoặc lấy các vị trí \(\{1,3\}\) từ \(S\) (còn \(\{2,4\}\) từ \(T\)). Đáp án \(2\).