[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 \text{ sign } j$,其中 $0 \leq i, j \leq n - 1$ 且 $i \neq j$,$\text{sign}$ 为 $\tt{<}$ 或者 $\tt{>}$,表示第 $i$ 个关卡必须在第 $j$ 个关卡前或后完成。
输出格式
对于每个数据,输出一行一个整数,为攻克关卡的顺序方案个数,$\bmod (10^9+7)$ 输出。
输入输出样例
输入样例 #1
2
5
0 < 2
1 < 2
2 < 3
2 < 4
4
0 < 1
0 < 2
0 < 3
输出样例 #1
4
6
说明
对于 $20\%$ 的数据有 $n \le 10$。
对于 $40\%$ 的数据有 $n \le 100$。
对于另外 $20\%$ 的数据有,保证数据中 sign 只会是 <,并且 $i<j$。
对于 $100\%$ 的数据有 $T \le 5$,$1 \le n \le 1000$。