先史文明研究センター (Investigation Center for Prehistoric Civilization, ICPC) は Icpca 古王国文明を調査してきた. 先日の Icpca の廃墟の発掘では石壁に刻まれたふたつの式を発見した. 式は n 種類の Icpca 文字 a1, ..., an と不等号 ('<' と '>') および括弧 ('(' と ')') に相当する記号からなるが,記述の都合上,以下ではこれらを英大文字や通常の記号で表すことにする. 式は以下の文法規則 (開始記号 E) に従っている.
E ::= F | '(' E '<' E ')' | '(' E '>' E ')' F ::= a1 | a2 | … | an
古王国とその文明についての多様な知見を総合した分析から,以下の評価規則が判明した.
発見されたふたつの式の値は等しいはずであることもわかった. 考えられる n! 種の全順序のうち,両式の値が等しくなるような全順序は何種類存在するだろうか.
入力は複数のデータセットからなる. 各データセットは次の形式で表される.
n
a1a2...an
S
T
各データセットは 4 行からなる. 1 行目には,Icpca 文字に対応する英大文字の種類数 n (1 ≤ n ≤ 16) が与えられる. 2 行目には,n 種の相異なる英大文字が区切りなしで与えられる. 3 行目と 4 行目には,それぞれ発見されたふたつの式 S と T が与えられる. S と T は共に 100 文字以内であり,上述の文法に従う.
入力の終わりは,ゼロひとつからなる行で表される. データセットの個数は 50 を超えない.
各データセットについて,発見されたふたつの式の値が等しくなるような全順序の種類数を 1 行に出力せよ.
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
1 0 6 300