Description

Welcome to SAO (Strange and Abnormal Online). This is a VR MMORPG with $n$ levels. However, deciding the order to challenge the levels is a big problem.

The game imposes $n-1$ constraints on the order of levels, such as level $i$ must be challenged before level $j$, or you can attempt level $l$ only after finishing level $k$. Moreover, if we ignore the directions of the constraints, then under these $n-1$ constraints, any two levels are connected in some way. That is, we cannot partition all levels into two nonempty disjoint subsets such that there is no constraint between the two subsets.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains an integer $n$, the number of levels. Then follow $n - 1$ lines, each in the form $i \text{ sign } j$, where $0 \leq i, j \leq n - 1$ and $i \neq j$, and $\text{sign}$ is $\tt{<}$ or $\tt{>}$, meaning level $i$ must be completed before (if $\text{sign}$ is $\tt{<}$) or after (如果 $\text{sign}$ is $\tt{>}$) level $j$.

Output Format

For each test case, output one integer on a single line: the number of valid orders to conquer the levels, output $\bmod (10^9+7)$.

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

4 
6

Hint

• For $20\%$ of the testdata, $n \le 10$.
• For $40\%$ of the testdata, $n \le 100$.
• For another $20\%$ of the testdata, it is guaranteed that $\text{sign}$ is only $\tt{<}$ and $i<j$.
• For $100\%$ of the testdata, $T \le 5$ and $1 \le n \le 1000$.

Translated by ChatGPT 5