Một chương trình bao gồm một chuỗi lệnh, mỗi lệnh thuộc một trong các dạng sau:

• \(1: \times d\). Trong đó \(d\) là một chữ số trong khoảng \([0,9]\).
• \(2: +s\). Trong đó \(s\) là tên của biến. Trong chương trình, tất cả các tên biến phải phân biệt.

Kết quả của một chương trình là biểu thức thu được sau khi áp dụng từng lệnh theo thứ tự, bắt đầu với \(0\). Ví dụ, kết quả của chương trình \([\times 3,+x, +y, \times 2, +z]\) là biểu thức \((0\times 3+x +y)\times 2+z=2\times x+2\times y+z\) . Các chương trình khác nhau có thể tạo ra các biểu thức giống nhau; ví dụ, \([+w,\times 0,+y,+x,\times 2,+z,\times 1]\) cũng sẽ tạo ra biểu thức \(2\times x+2\times y+z\).

Bessie và Elsie mỗi người có một chương trình gồm \(N (1\leq N \leq 2000)\) lệnh. Họ sẽ sắp xếp các lệnh này để tạo ra một chương trình mới có độ dài \(2N\). Lưu ý rằng có \(\frac {(2N)!} {N! \times N!}\) cách để thực hiện việc này, nhưng không phải tất cả các trường hợp sẽ tạo ra kết quả khác nhau.

Đếm số biểu thức phân biệt có thể được tạo ra bằng cách sắp xếp các lệnh trên, kết quả \(\% (1e9+7)\).

Mỗi bộ test chứa \(T(1 \leq T \leq 10)\) test con. Dữ liệu đầu vào đảm bảo rằng tổng \(N\) trên tất cả test con không vượt quá \(2000\).

Input

• Dòng đầu tiên chứa số \(T\), số lượng test con.
• Dòng đầu tiên của mỗi test chứa số \(N\).
• Dòng thứ hai của mỗi test chứa chương trình của Bessie, được biểu thị bằng một xâu có độ dài \(N\). Mỗi ký tự, hoặc là một chữ số \(𝑑∈[0,9]\) biểu thị lệnh loại 1, hoặc ký tự \(+\) biểu thị lệnh loại 2.
• Dòng thứ ba của mỗi test chứa chương trình của Elsie, có cùng định dạng như của Bessie.
• Trong mỗi test, tên biến của các lệnh là khác nhau. Tên biến không được cung cấp vì chúng không ảnh hưởng đến câu trả lời.

Output

• Số lượng các biểu thức phân biệt có thể được tạo ra, \(\%(1e9+7)\).

Scoring

• Subtask \(1\): \(N \leq 6\)
• Subtask \(2\): \(\sum N \leq 100\)
• Subtask \(3\): \(\sum N \leq 500\)
• Subtask \(4\): Không có điều kiện gì thêm.

Example

4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1

1
3
9
9