레이팅 미적용프로그램은 명령어들의 수열로 이루어지며, 각 명령어는 다음 형태 중 하나이다.
- \(\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\))의 명령어로 이루어진 프로그램을 가지고 있다. 두 소는 이 프로그램들을 서로 끼워 넣어(interleave) 길이 \(2N\)의 새 프로그램을 만들 것이다. 이렇게 하는 방법은 \(\frac{(2N)!}{N!\times N!}\)가지가 있지만, 그런 프로그램들을 실행했을 때 모두 서로 다른 식이 나오는 것은 아니다.
베시와 엘시의 프로그램을 끼워 넣어 만든 프로그램을 실행했을 때 나올 수 있는 서로 다른 식의 개수를 \(10^9+7\)로 나눈 나머지를 구하여라.
각 입력은 독립적으로 풀어야 하는 \(T\)개(\(1\le T\le 10\))의 테스트 케이스를 포함한다. 모든 테스트 케이스에 걸친 \(N\)의 합은 \(2000\)을 초과하지 않음이 보장된다.
Problem credits: Benjamin Qi
채점 방식
- 입력 2는 \(N\le 6\)을 만족한다.
- 입력 3-5에서는 모든 \(N\)의 합이 최대 \(100\)이다.
- 입력 6-8에서는 모든 \(N\)의 합이 최대 \(500\)이다.
- 입력 9-16은 추가 제약이 없다.
Problem credits: Benjamin Qi
입력의 첫째 줄에 테스트 케이스의 수 \(T\)가 주어진다.
각 테스트 케이스의 첫째 줄에 \(N\)이 주어진다.
각 테스트 케이스의 둘째 줄에는 길이 \(N\)의 문자열로 표현된 베시의 프로그램이 주어진다. 각 문자는 유형 1의 명령어를 나타내는 숫자 \(d\in [0,9]\)이거나, 유형 2의 명령어를 나타내는 문자 \(+\)이다.
각 테스트 케이스의 셋째 줄에는 베시의 것과 같은 형식으로 엘시의 프로그램이 주어진다.
한 테스트 케이스 안에서 모든 명령어의 변수 이름은 서로 다르다. 변수의 실제 이름은 답에 영향을 주지 않으므로 제공되지 않는다.
베시와 엘시의 프로그램을 끼워 넣어 만든 프로그램을 실행했을 때 나올 수 있는 서로 다른 식의 개수를 \(10^9+7\)로 나눈 나머지를 출력한다.
4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+11
3
9
9For the first test case, the two possible interleaved programs are
\([\times 1, \times 0]\) and \([\times 0,\times 1]\). These will both produce the
expression \(0\) when executed.
For the second test case, executing an interleaving of \([\times 1,\times 2, +x]\)
and \([+y, \times 0,\times 2]\) could produce one of the expressions \(0\), \(x\), or
\(2\times x\).