题目描述

某个大型冒险系统中共有 $n$ 个任务，编号为 $0,1,\cdots,n-1$。玩家需要为这些任务安排一个完成顺序。

不过，任务之间存在 $n-1$ 条先后限制。每条限制会说明某个任务必须早于另一个任务完成，或者某个任务必须晚于另一个任务完成。

如果暂时忽略这些限制的方向，只把它们看成任务之间的关联关系，那么这 $n-1$ 条限制会把所有任务连成一个整体。也就是说，不存在一种方法可以把全部任务分成两个非空且互不相交的集合，使得两个集合之间没有任何限制相连。

现在给定所有限制，请你计算一共有多少种合法的任务完成顺序。答案需要对 $10^9+7$ 取模。

输入格式

第 $1$ 行包含一个整数 $T$，表示数据组数。

对于每组数据：

第 $1$ 行包含一个整数 $n$，表示任务数量。

接下来 $n-1$ 行，每行形如 $i$ $\text{op}$ $j$，其中 $0 \le i,j \le n-1$ 且 $i \ne j$，$\text{op}$ 为 < 或 >：

• 若为 $i$ < $j$，表示任务 $i$ 必须在任务 $j$ 之前完成；
• 若为 $i$ > $j$，表示任务 $i$ 必须在任务 $j$ 之后完成。

输出格式

对于每组数据，输出一行一个整数，表示合法完成顺序的数量对 $10^9+7$ 取模后的结果。

样例

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

4
6

样例说明

数据范围

• 对于 $20$ 的数据：$n \le 10$。
• 对于 $40$ 的数据：$n \le 100$。
• 对于另外 $20$ 的数据：保证数据中 $\text{op}$ 只会是 <，并且 $i<j$。
• 对于 $100$ 的数据：$T \le 5$，$1 \le n \le 1000$。