Програма складається з послідовності інструкцій, кожна з яких має одну з наступних форм:

1. \(\times d\), де \(d\) це цифра в інтервалі \([0,9]\)
2. \(+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\) у всіх тестах не перевищить \(2000\).

Формат вхідних даних

Перший рядок введення містить \(T\) кількість тестів.

Перший рядок кожного тесту містить число \(N\).

Другий рядок кожного тесту містить програму Бесі, представлену рядком довжини \(N\). Кожен символ або цифра \(d\in [0,9]\), що представляє інструкцію типу 1, або символ \(+\), який представляє інструкцію типу 2.

Третій рядок кожного тесту містить програму Ельзи, у тому форматі як і в Бесі.

Всередині тесту імена змінних серед усіх інструкцій різні. Зауважимо, що реальні імена не вводяться, оскільки вони впливають результат.

Формат вихідних даних

Кількість різних виразів, які можуть бути здійснені виконанням перемішаних програм Бесі та Ельзи за модулем \(10^9+7\).

Приклад вхідних даних

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

Приклад вихідних даних

1
3
9
9

Для першого тесту дві можливі змішані програми є: \([\times 1, \times 0]\) І \([\times 0, \times 1]\). Обидві вони відповідь \(0\) в результаті обчислення.

Для другого тесту, виконання перемішаних програм \([\times 1,\times 2, +x]\) і \([+y, \times 0,\times 2]\)

можуть зробити один із виразів \(0\), \(x\) або \(2\times x\).

ОЦІНЮВАННЯ:

• У тесті 2 \(N\le 6\).
• У тестах 3-5, сума всіх \(N\) не більше \(100\).
• У тестах 6-8, сума всіх \(N\) не більше \(500\).
• У тестах 9-16 немає додаткових обмежень.