Icpca 文字

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

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

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

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

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

Input

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

n
a₁a₂...a_n
S
T

各データセットは 4 行からなる． 1 行目には，Icpca 文字に対応する英大文字の種類数 n (1 ≤ n ≤ 16) が与えられる． 2 行目には，n 種の相異なる英大文字が区切りなしで与えられる． 3 行目と 4 行目には，それぞれ発見されたふたつの式 S と T が与えられる． S と T は共に 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

---