Problem H: Oh, My Goat!

太郎君は、次郎君に古文のノートを借りた。 明日の古文の宿題を写させてもらうためだ。 太郎君は、用心深い性格をしているため、万が一のことを考えて、近所のコンビニで次郎君のノートのコピーを取って自宅へ帰った。

太郎君は、自宅で宿題を始めようとしたときに、慌てた。 次郎君から借りたノートが鞄に入っていなかったからだ。 どうやら、コンビニに忘れてきてしまったようだ。

太郎君は、急いでコンビニに引き返した。 コピー機とその周辺を懸命に捜索したが、ノートを見つけることはできなかった。

困り果てた太郎君は、コンビニの店長に助けを求めた。 余談だが、店長は地球環境に優しい人で、白ヤギさんを飼っている。 店長は、地球環境に気を配る心遣いを持っているため、常日頃から、ペットの白ヤギさんに、餌としてコピー機周辺の客の忘れものを与えている。 店長によると、ノートは、今晩の白ヤギさんの晩御飯であり、白ヤギさんは現在食事中だそうである。 太郎君は白ヤギさんに頼みこみ、食べかけのノートを取り返すことはできたが、ノートはビリビリに破れぼろぼろである。

太郎君は、急いで自宅に引き返した。 自室の机とその周辺を懸命に捜索したが、ノートのコピーを見つけることはできなかった。

困り果てた太郎君は、お母さんに助けを求めた。 余談だが、太郎君のお母さんは地球環境に優しい人で、黒ヤギさんを飼っている。 太郎君のお母さんは、地球環境に気を配る心遣いを持っているため、常日頃から、ペットの黒ヤギさんに、餌として太郎君の宿題を与えている。 お母さんによると、ノートのコピーは、今晩の黒ヤギさんの晩御飯であり、黒ヤギさんは現在食事中だそうである。 太郎君は黒ヤギさんに頼みこみ、食べかけのノートを取り返すことはできたが、ノートのコピーはビリビリに破れぼろぼろである。

次郎君のノートとそのコピーをビリビリのぼろぼろにされてしまった太郎君は、ノートを可能な限り復元しようと考えた。 そこで、繋がりそうなノートの切れ端同士を繋ぎ合わせて、「繋ぎ合せたノート」を作成した。 同様に、繋がりそうなノートのコピーの切れ端同士を繋き合わせて、「繋ぎ合せたノートのコピー」を作成した。

太郎君は、あらゆる可能性を考えるために、繋がりそうな切れ端同士をつなぎ合わせた。 このため、1つの切れ目に2つ以上の切れ端が繋がれてしまった箇所もあった。

繋ぎ合わせ方の例を図1に示す。 図1は、7つの切れ端と6つの切れ目からなる。

図1

切れ端"haru"と"natsu"に続く切れ目には、切れ端"wa"が繋がり、文章が合流している。 切れ端"wa"に続く切れ目には、切れ端"ake"と"saron"が繋がり、文章が分岐している。 このような合流や切れ端があるため、図1は次のような4つの文章を表す。

• haruwaakebono
• haruwasaronpusu
• natsuwaakebono
• natsuwasaronpusu

太郎君の代わりに、「繋ぎ合わせたノート」と「繋ぎ合わせたノートのコピー」の2つを入力として受け取って、両方に共通して現れる文章の数を求めるプログラムを作成せよ。

Input

入力の1行目では、データセットの数T(1 ≤ T ≤ 100)が与えられる。

データセットは、「繋ぎ合せたノート」の情報と、「繋ぎ合せたノートのコピー」の情報から成る。

「繋ぎ合せたノート」の情報として、 1行目にn(2 ≤ n ≤ 500)とm(1 ≤ m ≤ 600)が与えられる。 nは、切れ端と切れ端を繋ぎ合せる切れ目の数である。 続くm行で繋ぎ合せ方が与えられる。 各行は、切れ端の上端に繋がる切れ目の番号a、切れ端の下端につながる切れ目の番号b、切れ端を表す文字列sからなる。 ただし、0 ≤ a < b < nが満たされる。 sは長さが1以上5以下の文字列で、アルファベットの小文字のみから成る。

「繋ぎ合せたノートのコピー」も「繋ぎ合せたノート」と同じ形式で与えられる。

なお、0番目の切れ目から繋ぎ合せ情報を辿り、n-1番目の切れ目に到達する過程で得られる文字列を連結したもののみを文章と呼ぶものとする。 また、それぞれの繋ぎ合せの中で同じ文章が2つ以上出現することはない。

Output

それぞれのデータセット毎に、答えの整数を1,000,000,007で割った余りを1行で出力せよ。

Sample Input

4
2 1
0 1 a
2 2
0 1 a
0 1 b
5 5
0 1 a
0 2 b
1 3 a
2 3 c
3 4 e
3 3
0 1 aa
0 2 bce
1 2 a
2 4
0 1 abc
0 1 def
0 1 ghi
0 1 jkl
2 4
0 1 ghi
0 1 jkl
0 1 mno
0 1 pqr
6 7
0 1 haru
0 1 natsu
1 2 wa
2 3 ake
2 4 saron
3 5 bono
4 5 pusu
5 4
0 1 haruw
1 2 aakeb
2 3 o
3 4 no

Output for Sample Input

1
1
2
1