프리오더 포스트오더

이진 트리를 인오더(in-order) 와 포스트오더(post-order) 로 순회한 결과가 주어지면 프리오더(pre-order) 순회 결과를 유일하게 복원할 수 있다. 마찬가지로 인오더와 프리오더 순회 결과가 주어지면 포스트오더 순회 결과도 복원할 수 있다. 하지만 프리오더와 포스트오더 순회 결과만 주어지면 인오더 순회 결과를 유일하게 복원할 수 없다.

실제로 같은 프리오더와 포스트오더를 갖는 서로 다른 이진 트리가 여러 개 존재할 수 있다. 예를 들어 자식이 하나뿐인 노드는 그 자식을 왼쪽에 둘 수도, 오른쪽에 둘 수도 있는데 두 경우의 프리오더와 포스트오더가 같아진다. 이런 현상은 이진 트리뿐 아니라 각 노드가 자식을 최대 $m$개까지 가질 수 있는 모든 $m$진 트리에서 나타난다.

$m$진 트리를 프리오더와 포스트오더로 순회한 결과가 주어졌을 때, 이 순회 결과를 갖는 서로 다른 트리의 개수를 출력하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 다음과 같은 형식으로 주어진다.

m s1 s2

여기서 $m$은 각 노드가 가질 수 있는 자식의 최대 개수, $s1$은 프리오더 순회 결과, $s2$는 포스트오더 순회 결과이다. ($1 \le m \le 20$, $1 \le |s1| = |s2| \le 26$)

$s1$의 길이가 $k$이면 트리의 노드에는 알파벳 소문자 첫 $k$개가 각각 정확히 한 번씩 사용된다. 입력의 마지막 줄에는 $0$이 하나 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다, 주어진 프리오더와 포스트오더 순회 결과를 갖는 $m$진 트리의 개수를 한 줄에 출력한다. 정답은 항상 부호 있는 32비트 정수 범위 안에 있으며, 입력으로 주어진 순회 결과를 갖는 트리는 적어도 하나 존재함이 보장된다.