문제
프로그램은 일련의 명령어로 구성되며 각 명령어는 다음 형식 중 하나를 갖습니다.
1. ×d, 여기서 d는 [0,9] 범위의 한 자리 숫자입니다.
2. +s, 여기서 s는 변수 이름을 나타내는 문자열입니다. 프로그램에 나타나는 모든 변수 이름은 동일하지 않습니다.
프로그램 실행 결과는 각 명령어를 차례로 적용한 0으로 시작하는 표현식으로 나옵니다.
예를 들어, [×3,+x,+y,×2,+z] 프로그램을 실행하면 표현식 (0×3+x+y)×2+z=2×x+2×y+z가 됩니다.
예를 들어 [+w,×0,+y,+x,×2,+z,×1]을 실행하면 2×x+2×y+z 식이 생성됩니다.
권수와 경수는 각각 N개의 명령어의 프로그램을 가지고 있습니다.
그들은 이 프로그램의 명령어를 교차로 사용하여 2N개의 명령어로 구성된 새로운 프로그램을 만듭니다.
총 (2N)!/(N!*N!)개의 방법이 있지만, 이러한 모든 프로그램이 실행 후 다른 표현식을 얻는 것은 아닙니다.
권수와 경수의 프로그램으로 얻을 수 있는 표현식 중 고유한 표현식의 수를 세십시오.
입력
첫 번째 줄에는 테스트 케이스의 수인 T가 입력됩니다. (1≤T≤10)
각 테스트 케이스의 첫 번째 줄에는 N이 입력됩니다. (1≤N≤2000)
각 테스트 케이스의 두 번째 줄에는 길이가 N인 문자열로 표시되는 권수의 프로그램이 입력됩니다.
각 문자는 유형 1의 명령어를 나타내는 단일 숫자 d∈[0,9] 또는 유형 2의 명령어를 나타내는 문자 +입니다.
각 테스트 케이스의 세 번째 줄에는 길이가 N인 문자열로 표시되는 경수의 프로그램이 입력됩니다.
각 문자는 유형 1의 명령어를 나타내는 단일 숫자 d∈[0,9] 또는 유형 2의 명령어를 나타내는 문자 +입니다.
각 테스트 케이스의 경우 모든 지시문 내의 변수 이름이 동일하지 않습니다.
답변에 영향을 미치지 않기 때문에 실제 이름은 여기에 표시되지 않습니다.
모든 하위 테스트 케이스에서 N의 합이 2000을 초과하지 않도록 보장합니다.
출력
권수와 경수의 프로그램으로 얻을 수 있는 표현식 중 고유한 표현식의 수를 109+7로 나눈 나머지를 출력하시오.
예제1
4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1
1
3
9
9