[HEOI2013]SAO

题目描述

Welcome to SAO ( Strange and Abnormal Online)。这是一个 VR MMORPG, 含有 n 个关卡。但是,挑战不同关卡的顺序是一个很大的问题。 有 n – 1 个对于挑战关卡的限制,诸如第 i 个关卡必须在第 j 个关卡前挑战, 或者完成了第 k 个关卡才能挑战第 l 个关卡。并且,如果不考虑限制的方向性, 那么在这 n – 1 个限制的情况下,任何两个关卡都存在某种程度的关联性。即, 我们不能把所有关卡分成两个非空且不相交的子集,使得这两个子集之间没有任 何限制。

输入输出格式

输入格式


第一行,一个整数 T,表示数据组数。 对于每组数据,第一行一个整数 n,表示关卡数。接下来 n – 1 行,每行为 “i sign j”,其中 0 ≤ i, j ≤ n – 1 且 i ≠ j,sign 为“<”或者“>”,表示第 i 个关卡 必须在第 j 个关卡前/后完成。

输出格式


对于每个数据,输出一行一个整数,为攻克关卡的顺序方案个数,mod 1,000,000,007 输出。

输入输出样例

输入样例 #1

2 
5 
0 < 2 
1 < 2 
2 < 3 
2 < 4 
4 
0 < 1 
0 < 2 
0 < 3

输出样例 #1

4 
6

说明

对于 20%的数据有 n ≤ 10。 对于 40%的数据有 n ≤ 100。 对于另外 20%的数据有,保证数据中 sign 只会是<,并且 i < j。 对于 100%的数据有 T ≤ 5,1 ≤ n ≤ 1000。