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个关卡前/后完成
T ≤ 5，1 ≤ n ≤ 1000
对于每个数据，输出一行一个整数，为攻克关卡的顺序方案个数，mod1,000,000,007输出。
对于 20%的数据有 n ≤ 10。
对于 40%的数据有 n ≤ 100。
对于另外 20%的数据有，保证数据中 sign 只会是<，并且 i < j。
对于 100%的数据有 T ≤ 5，1 ≤ n ≤ 1000。