7167: BZOJ3167:[Heoi2013]Sao

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

WelcometoSAO(StrangeandAbnormalOnline)。这是一个VRMMORPG,含有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个关卡前/后完成。 T≤5,1≤n≤1000


输出格式

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


样例输入

5
10
5 > 8
5 > 6
0 < 1
9 < 4
2 > 5
5 < 9
8 < 1
9 > 3
1 < 7
10
6 > 7
2 > 0
9 < 0
5 > 9
7 > 0
0 > 3
7 < 8
1 < 2
0 < 4
10
2 < 0
1 > 4
0 > 5
9 < 0
9 > 3
1 < 2
4 > 6
9 < 8
7 > 1
10
0 > 9
5 > 6
3 > 6
8 < 7
8 > 4
0 > 6
8 > 5
8 < 2
1 > 8
10
8 < 3
8 < 4
1 > 3
1 < 9
3 < 7
2 < 8
5 > 2
5 < 6
0 < 9

样例输出

2580
3960
1834
5208
3336

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: