Программа состоит из последовательности инструкций, каждая из которых
имеет одну из следующих форм:
- \(\times d\), где \(d\) это цифра в интервале \([0,9]\)
- \(+s\), где \(s\) это строка, обозначающая имя переменной. В программе все переменные
различны.
Результат выполнения программы определяется как выражение - результат выполнения
всех инструкций в порядке ввода , начиная с \(0\). Например, результаты выполнения программы
\([\times 3,+x,+y,\times 2,+z]\) есть выражение \((0\times 3+x+y)\times 2+z=2\times x+2\times y+z\).
При выполнении различные программы могут формировать одни и те же выражения. Например,
исполнение программы \([+w,\times 0,+y,+x,\times 2,+z, \times 1]\) также в результате
даёт выражение \(2\times x+2\times y+z\).
У Беси и Эльзы есть по программе из \(N\) (\(1\le N\le 2000\)) инструкций. Они
объединяют инструкции этих программ, чтобы получить новую программу длиной \(2N\).
Заметим, что всего имеется \(\frac{(2N)!}{N!\times N!}\) способов объединить программы, но
но не все из этих программ дадут различные результаты.
Вычислите количество различных выражений, которые могут быть получены
исполнением объединённых программ Беси и Эльзы по модулю \(10^9+7\).
Каждый ввод состоит из \(T\) (\(1\le T\le 10\)) тестов, которые требуется решать независимо.
Гарантируется, что сумма \(N\) во всех \(T\) тестах не превысит \(2000\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(T\), количество тестов.
Первая строка каждого теста содержит число \(N\).
Вторая строка каждого теста содержит программу Беси, представленную строкой длины \(N\).
Каждый символ или цифра \(d\in [0,9]\), представляющая инструкцию типа 1, или символ \(+\),
представляющий инструкцию типа 2.
Третья строка каждого теста содержит программу Эльзы, в том же формате как и у Беси.
Внутри теста, имена переменных среди всех инструкций различны. Заметим, что
реальные имена не вводятся, поскольку они не влияют на результат.
ФОРМАТ ВЫВОДА (НА ЭКРАН / stdout):
Количество различных выражений, которые могут быть произведены исполнением
перемешанных программ Беси и Эльзы по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1
|
1
3
9
9
|