Lập Trình Cặp

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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

Nhân: $\times d$ (với $d \in [0, 9]$ )
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ả $2 x + 2 y + 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 $2 N$ 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 \leq T \leq 10$
$1 \leq N \leq 2000$
Tổng $N$ qua tất cả test case $\leq 2000$
Tất cả tên biến là phân biệt

Ví dụ

Input	Output	Giải thích
4 1 0 1 3 12+ +02 3 0++ ++9 4 5+++ +6+1	1 3 9 9	Test 1: Nhân với 0 rồi nhân với 1 luôn cho 0. Test 2: Ba cách xen kẽ khác nhau tạo 3 biểu thức phân biệt.

Bình luận

Không có bình luận tại thời điểm này.