Icpca 문자

그림 D-1 돌벽에 새겨진 두 식의 사진.

선사 문명 연구소(ICPC)에서는 고대 Icpca 왕국의 문명을 연구해 왔다. 최근 발굴에서 Icpca 유적의 돌벽에 새겨진 두 식이 발견되었다. 이 식들은 n개의 서로 다른 Icpca 문자 a1, ..., an, 부등호('<', '>')에 해당하는 기호, 괄호('(', ')')로 이루어져 있다. 설명을 쉽게 하기 위해 이들을 로마자 대문자와 일반 기호로 나타낸다. 식은 시작 기호 E에 대한 다음 문법 규칙을 따른다.

  E ::= F | '(' E '<' E ')' | '(' E '>' E ')'
  F ::= a1 | a2 | … | an

고대 왕국과 그 문명에 대한 여러 지식을 통합한 분석으로 다음 평가 규칙이 밝혀졌다.

• 문자 a1, ..., an의 집합 위에 전순서 관계가 정의된다.
• 식이 문자 하나로만 이루어져 있으면 그 식의 값은 그 문자이다.
• 값이 ai인 식 P와 값이 aj인 식 Q에 대해, 식 (P<Q)의 값은 전순서에서 앞서는 쪽인 ai 또는 aj이다. 두 문자가 같으면 그 문자이다.
• 마찬가지로, 값이 ai인 식 P와 값이 aj인 식 Q에 대해, 식 (P>Q)의 값은 전순서에서 뒤에 오는 쪽인 ai 또는 aj이다. 두 문자가 같으면 그 문자이다.

발견된 두 식의 값은 서로 같아야 한다는 사실도 밝혀졌다. n!개의 가능한 전순서 중 두 식의 값이 같아지게 하는 서로 다른 전순서는 몇 개인가?

입력은 여러 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식이다.

n a1a2...an S T

각 데이터셋은 네 줄로 이루어진다. 첫째 줄에는 Icpca 문자에 대응하는 서로 다른 로마자 대문자의 개수 n (1 ≤ n ≤ 16)이 주어진다. 둘째 줄에는 n개의 서로 다른 로마자 대문자가 공백 없이 주어진다. 셋째 줄과 넷째 줄에는 각각 발견된 두 식 S와 T가 주어진다. S와 T는 모두 위에 주어진 문법을 따르며, 각각 100자를 넘지 않는다.

입력의 끝은 0만 포함된 줄로 표시된다. 데이터셋의 개수는 50개를 넘지 않는다.

각 데이터셋에 대해 두 식의 값이 같아지게 하는 서로 다른 전순서의 개수를 한 줄에 출력한다.