[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 输出。

7
5 
0 < 2 
1 < 2 
2 < 3 
2 < 4 
4 
0 < 1 
0 < 2 
0 < 3
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

4 
6
2580
3960
1834
5208
3336

提示

对于 $20\%$ 的数据有 $n \le 10$。

对于 $40\%$ 的数据有 $n \le 100$。

对于另外 $20\%$ 的数据有，保证数据中 sign 只会是 <，并且 $i<j$。

对于 $100\%$ 的数据有 $T \le 5$，$1 \le n \le 1000$。