ICPCの国内予選に備えて問題を解いていた僕は, その日3つ目のAcceptを貰ったところでキーボードを叩く手を止めた. 時計を見れば, もう日付が変わろうかという時刻だ. 紅茶とお菓子で一服して, 今日はもう寝ることにしよう. そう思って僕はキッチンへと向かった.
ダージリンのかぐわしい香りがキッチンを満たした頃, 妹がやってきた. 受験生である彼女は今日もこんな時間まで真面目に勉強していたようだ. 僕は彼女を誘って, 小さな深夜のお茶会を開くことにした.
都合の良いことに, キッチンには4つのお菓子があった. これをただ2人で分けるのもつまらないので, 僕はこのお菓子を賭けて簡単なゲームをしないかと提案した. そのゲームの内容を説明しよう.
まず最初に, 僕はどのノードも0個または2個の子を持つような二分木を書く. 次に, その木の葉に当たる(つまり, 子を持たない)ノードに, それぞれ S = {a, b, c, d} の任意の部分集合を書き込む. 4つのお菓子は, それぞれ a, b, c, d に対応する.
最後に妹は, 木の内部接点(つまり、2つの子を持つ)ノードに 'A', 'O', 'X' のいずれかの文字を書き込む.
妹は, 木の根にあたるノードが示すお菓子を得る. ただし, ノードが示すお菓子とは,
のことである. ここで、sl はそのノードの左の子ノードが示すお菓子, sr はそのノードの右の子ノードが示すお菓子を指す. 2つの集合の対称差は, どちらか一方の集合にのみ含まれるような元から成る集合である.
このゲームに妹は乗ってきた. それどころか, お菓子を4つとも巻き上げてやろうと目を輝かせている. 出来れば僕の分も残しておいてくれると嬉しいのだけれども.
僕が書いた木に対して, 妹が全てのお菓子を得られるような内部接点の書き込み方は, いったい何通りあるだろうか？
入力ファイルは、複数のデータセットを含む.
データセットの最初の行には, 木の情報が与えられる. 木の記述は,
"(" <左部分木の記述> <一つのスペース> <右部分木の記述> ")"
または,
<一つの数字>
のどちらかの形式を取る. 前者が内部接点の記述, 後者が葉の記述である.
次の行は1つの整数 N (N < 10) を含み, 続く N 行に葉に書き込まれた部分集合の情報が与えられる.
部分集合の情報は, 空白文字で区切られた4つの数字で表される. 4つの文字はそれぞれ, その部分集合が a, b, c, d を含むかどうかを表す. 含むならば 1 が、含まないならば 0 が与えられる.
葉の記述として与えられた数字が n であるとき、その葉に書き込まれた部分集合はこれら N 個のうち n 番目のものである. 1 ≤ n ≤ N と仮定してよい.
与えられる木は、最大 8 個の内部接点を含む.
木の記述の代わりに与えられる "END" という文字列が, 入力の終わりを表す.
各データセットについて, 妹が全てのお菓子を得られるような内部接点の書き込み方の数を、一行に出力せよ.
(1 2) 2 0 1 0 1 1 0 1 0 ((1 2) 3) 3 1 1 0 0 1 0 1 0 0 0 0 1 END
2 2