Lập Trình Cặp

Một chương trình gồm các lệnh thuộc hai loại:

1. Nhân: $\times d$ (với $d\in [0,9]$)
2. Cộng biến: $+s$ (với $s$ là tên biến)

Thực thi bắt đầu từ $0$ và áp dụng các lệnh tuần tự. Ví dụ: $[\times 3,+x,+y,\times 2,+z]$ cho kết quả $2x+2y+z$.

Bessie và Elsie mỗi người có một chương trình gồm $N$ lệnh. Họ xen kẽ hai chương trình để tạo thành một chương trình mới gồm $2N$ lệnh (giữ nguyên thứ tự tương đối trong mỗi chương trình). Các cách xen kẽ khác nhau có thể cho cùng một biểu thức.

Hãy đếm số biểu thức phân biệt có thể tạo ra, modulo ${10}^9+7$.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ (số test case)
• Với mỗi test case:
  • Dòng 1: Số nguyên $N$
  • Dòng 2: Chương trình của Bessie (xâu độ dài $N$ gồm các chữ số và '+')
  • Dòng 3: Chương trình của Elsie (xâu độ dài $N$ gồm các chữ số và '+')

Dữ liệu ra

Với mỗi test case, in số biểu thức phân biệt modulo ${10}^9+7$.

Ràng buộc

• $1\le T\le 10$
• $1\le N\le 2000$
• Tổng $N$ qua tất cả test case $\le 2000$
• Tất cả tên biến là phân biệt

Ví dụ