英世博士は日々研究を行い、新しい薬を開発しようとしています。新薬を開発するためには、色々な物質を組み合わせて薬を作り試験を行い、良い薬を見つけなければなりません。様々な組み合わせを試していくうちに、英世博士は物質の組み合わせが樹形図で表せることを突き止めました。
右の図は、薬の調合を表す樹形図の例です。図の中で丸く囲まれたものを物質ノード、三角で囲まれたものを選択ノードと呼びます。物質ノードは物質を表します。選択ノードは、物質の選択を表すもので、それ自体は物質を表しません。選択ノードには or 型(∨が付いたもの)と alt 型(⇔が付いたもの)の2種類があります。また ? が付いたノードは、それがオプションであることを表します。ただし、選択ノードの子ノード(下向きの枝の先にあるノード)がオプションになることはありません。樹形図に現れる異なる物質ノードは、それぞれ別の物質を表すものとします。
薬の調合を行うときは、樹形図の一番上のノードからはじめて、順々にノードをたどっていきながら以下のようにしてノードを選んでいきます。
あるノードが選ばれたときだけ、そのノードから下に向かう枝をそれぞれたどっていきます。選ばれなければ、それらをたどることはありません。
あなたは英世博士から、薬の物質の組み合わせを表す樹形図を受け取り、組み合わせの数が全部で何通りあるか求めるよう指示されました。樹形図が与えられたとき、組み合わせの総数を出力するプログラムを作成してください。
入力は以下の形式で与えられる。
N node1 node2 : nodeN s1 t1 s2 t2 : sN-1 tN-1
1行目にノードの数 N (1 ≤ N ≤ 1000) が与えられる。続く N 行に、i 番目のノードの情報 nodei が与えられる。1番目のノードを樹形図の一番上のノードとする。続く N-1 行に si 番目のノードからその子である ti 番目のノード (1 ≤ si ≠ ti ≤ N) へ向かう枝が与えられる。t1 から tN-1 までには、2 から N までの数が一度だけ現れる。
ノードの情報は以下の形式である。
入力から得られる樹形図は、以下の条件を満たす。
与えられた樹形図から得られるすべての組み合わせの総数を1行に出力する。ただし、出力すべき値は非常に大きくなりうるので、代わりに 1,000,000,007 で割った余りを出力する。
12 A E E E R? E? E? E E E E? E 1 2 1 3 1 4 2 5 4 6 4 7 5 8 5 9 7 10 7 11 11 12
11
10 E R? E R E E A E E E 1 2 1 7 2 3 2 4 4 5 4 6 7 8 7 9 7 10
24