A6705 | $「HEOI2013」SAO$

时间限制3s

内存限制256MB

通过 / 提交0/0

题目描述

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 \ne j$，$\text{sign}$ 为 < 或者 >，表示第 $i$ 个关卡必须在第 $j$ 个关卡前/后完成。

对于每个数据，输出一行一个整数，为攻克关卡的顺序方案个数，$\bmod 1000000007$ 输出。

输入 #1

输出 #1

4
6

C++ 编辑器

输入

输出