acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem D

Icpca 文字

図 D-1 石壁に刻まれたふたつの式の写真.

先史文明研究センター (Investigation Center for Prehistoric Civilization, ICPC) は Icpca 古王国文明を調査してきた. 先日の Icpca の廃墟の発掘では石壁に刻まれたふたつの式を発見した. 式は n 種類の Icpca 文字 a1, ..., an と不等号 ('<' と '>') および括弧 ('(' と ')') に相当する記号からなるが,記述の都合上,以下ではこれらを英大文字や通常の記号で表すことにする. 式は以下の文法規則 (開始記号 E) に従っている.

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

古王国とその文明についての多様な知見を総合した分析から,以下の評価規則が判明した.

  • 文字 a1, ..., an の集合にはある全順序が定められている.
  • 式が文字ひとつからなるとき,その値はその文字そのものである.
  • ふたつの式 PQ の値がそれぞれ aiaj であるとき,式 (P<Q) の値は,aiaj のうち全順序で先に来る方の文字である.両者が同じ文字なら値はその文字である.
  • 同様に,ふたつの式 PQ の値がそれぞれ aiaj であるとき,式 (P>Q) の値は,aiaj のうち全順序で後に来る方の文字である.両者が同じ文字なら値はその文字である.

発見されたふたつの式の値は等しいはずであることもわかった. 考えられる n! 種の全順序のうち,両式の値が等しくなるような全順序は何種類存在するだろうか.

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

n
a1a2...an
S
T

各データセットは 4 行からなる. 1 行目には,Icpca 文字に対応する英大文字の種類数 n (1 ≤ n ≤ 16) が与えられる. 2 行目には,n 種の相異なる英大文字が区切りなしで与えられる. 3 行目と 4 行目には,それぞれ発見されたふたつの式 ST が与えられる. ST は共に 100 文字以内であり,上述の文法に従う.

入力の終わりは,ゼロひとつからなる行で表される. データセットの個数は 50 を超えない.

Output

各データセットについて,発見されたふたつの式の値が等しくなるような全順序の種類数を 1 行に出力せよ.

Sample Input

3
CIP
((I<C)>(P<C))
(P>C)
2
AB
(A<B)
(A>B)
3
ANY
((A<N)<Y)
((N<Y)<((A<A)<N))
6
ANSWER
A
((E>(A>((E<W)>(N<S))))>(A<W))
0

Output for the Sample Input

1
0
6
300
(End of Problem D) A B C D E F G H