페어 프로그래밍

프로그램은 명령어들의 나열이며, 각 명령어는 다음 두 형태 중 하나이다:

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$을 넘지 않는다.

각 테스트 케이스의 첫 줄에는 $N$이 주어진다.

둘째 줄에는 베시의 프로그램이 길이 $N$인 문자열로 주어진다. 각 문자는 첫 번째 형태의 명령어를 나타내는 숫자 $d\in [0,9]$이거나, 두 번째 형태의 명령어를 나타내는 문자 $+$이다.

셋째 줄에는 엘시의 프로그램이 베시의 것과 같은 형식으로 주어진다.

한 테스트 케이스 안의 모든 명령어에서 변수 이름은 서로 다르다. 변수의 실제 이름은 주어지지 않으며, 답에 영향을 주지 않는다.

베시와 엘시의 섞인 프로그램을 실행했을 때 나올 수 있는 서로 다른 식의 개수를 $10^9+7$로 나눈 나머지를 출력한다.

첫 번째 테스트 케이스에서 가능한 섞인 프로그램은 $[\times 1, \times 0]$과 $[\times 0,\times 1]$ 두 가지이다. 둘 다 실행하면 식 $0$이 나온다.

두 번째 테스트 케이스에서 $[\times 1,\times 2, +x]$와 $[+y, \times 0,\times 2]$를 섞어 실행하면 식 $0$, $x$, $2\times x$ 중 하나가 나올 수 있다.