新薬開発

英世博士は日々研究を行い、新しい薬を開発しようとしています。新薬を開発するためには、色々な物質を組み合わせて薬を作り試験を行い、良い薬を見つけなければなりません。様々な組み合わせを試していくうちに、英世博士は物質の組み合わせが樹形図で表せることを突き止めました。

右の図は、薬の調合を表す樹形図の例です。図の中で丸く囲まれたものを物質ノード、三角で囲まれたものを選択ノードと呼びます。物質ノードは物質を表します。選択ノードは、物質の選択を表すもので、それ自体は物質を表しません。選択ノードには or 型（∨が付いたもの）と alt 型（⇔が付いたもの）の２種類があります。また ? が付いたノードは、それがオプションであることを表します。ただし、選択ノードの子ノード（下向きの枝の先にあるノード）がオプションになることはありません。樹形図に現れる異なる物質ノードは、それぞれ別の物質を表すものとします。

薬の調合を行うときは、樹形図の一番上のノードからはじめて、順々にノードをたどっていきながら以下のようにしてノードを選んでいきます。

• たどり着いたノードがオプションでない物質ノードなら、それを必ず選ぶ。
• オプションの物質ノードなら、それを選ぶかどうかは任意。
• or 型の選択ノードなら、その子から少なくとも一つを選ぶ。ただし、その選択ノードがオプションなら、子を一つも選ばなくてもよい。
• alt 型の選択ノードなら、その子から一つだけを選ぶ。ただし、その選択ノードがオプションなら、子を選ばなくてもよい。

あるノードが選ばれたときだけ、そのノードから下に向かう枝をそれぞれたどっていきます。選ばれなければ、それらをたどることはありません。

あなたは英世博士から、薬の物質の組み合わせを表す樹形図を受け取り、組み合わせの数が全部で何通りあるか求めるよう指示されました。樹形図が与えられたとき、組み合わせの総数を出力するプログラムを作成してください。

入力

入力は以下の形式で与えられる。

N
node1
node2
:
nodeN
s1 t1
s2 t2
:
sN-1 tN-1

１行目にノードの数 N (1 ≤ N ≤ 1000) が与えられる。続く N 行に、i 番目のノードの情報 node_i が与えられる。１番目のノードを樹形図の一番上のノードとする。続く N-1 行に s_i 番目のノードからその子である t_i 番目のノード (1 ≤ s_i ≠ t_i ≤ N) へ向かう枝が与えられる。t₁ から t_N-1 までには、2 から N までの数が一度だけ現れる。

ノードの情報は以下の形式である。

• E      オプションでない物質ノード。
• E?      オプションである物質ノード。
• type      オプションでない選択ノード。type は A か R のいずれかで、A は alt型、R は or 型を表す。
• type?      オプションである選択ノード。type の形式は同上。

入力から得られる樹形図は、以下の条件を満たす。

• 選択ノードは２つ以上の子ノードを持つ。
• 選択ノードの子ノードはオプションでない。
• 樹形図の一番上のノードはオプションでない。
• どのノードについても、子ノードの数は 10 を超えない。

出力

与えられた樹形図から得られるすべての組み合わせの総数を１行に出力する。ただし、出力すべき値は非常に大きくなりうるので、代わりに 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

---