Up and Down

시간 제한8초메모리 제한512 MB

요약

1부터 N까지의 순열 중에서 주어진 up-sequence와 down-sequence(오른쪽에서 가장 가까운 더 큰/작은 값까지의 거리)를 만족하는 순열의 개수를 센다. N은 17 이하이다.

문제

집합 {1, . . . , N}의 순열은 이 수들을 다시 나열한 것으로, 각 수는 정확히 한 번씩 나타난다. 순열의 up-sequence와 down-sequence를 다음과 같이 정의한다.

Up-sequence [u1, . . . , uN]: ui는 ai < ai+k가 성립하는 최소 양의 정수 k이다. 그러한 수가 없으면 ui = N + 1 − i이다.
Down-sequence [d1, . . . , dN]: di는 ai > ai+k가 성립하는 최소 양의 정수 k이다. 그러한 수가 없으면 di = N + 1 − i이다.

예를 들어 순열 [1, 4, 3, 2, 6, 5]가 주어지면 up-sequence는 [1, 3, 2, 1, 2, 1]이고 down-sequence는 [6, 1, 1, 3, 1, 1]이다.

일반적으로 같은 up-sequence와 down-sequence를 가지는 순열은 여러 개이다. 위 예에서 순열 [1, 5, 4, 2, 6, 3]과 [1, 5, 3, 2, 6, 4]도 같은 up-sequence와 down-sequence를 가진다.

주어진 up-sequence와 down-sequence에 대해 가능한 순열의 개수를 세어야 한다.

입력은 여러 데이터 세트로 이루어진다.

각 세트는 세 줄로 구성된다. 첫째 줄에는 양의 정수 N (N ≤ 17)이 주어진다. 다음 두 줄에는 각각 N개의 정수가 주어지며, 앞 줄은 up-sequence, 뒤 줄은 down-sequence이다. 정수는 공백으로 구분된다.

입력은 0 하나만 있는 줄로 끝난다. 이 줄은 처리하지 않는다.

각 세트에 대해 주어진 up-sequence와 down-sequence에 대응하는 순열의 개수를 한 줄에 출력한다.