题目链接：点我啊╭(╯^╰)╮

题目大意：

    树形图，求拓扑序数量

解题思路：

    $dp[i][j]$ 为 $i$ 在子树中拓扑序排名为 $j$ 的方案数
    有 $dp[x][p1]$、$dp[y][p2]$，$x$ 为 $y$ 的父亲，得到新的 $dp[x][p3]$
    则 $x$ 原来排在 $p1$，更新为 $p3$，$y$ 原来排在 $p2$、更新为 $p4$
    问题在于 $p3$ 的范围，和怎么求方案数

    若 $x$ 的拓扑序在 $y$ 之前，则 $p3<p4$
    $p1$ 左边的一定在 $p3$ 左边，$p1$ 右边的一定在 $p3$ 右边，$p2$ 右边的一定在 $p3$ 右边
    而 $p2$ 左边的可以任意摆，则 $p1-1\le p3-1\le p1-1+p2-1$，得到 $p1\le p3\le p1+p2-1$

    左边有 $p3-1$ 个点，有 $p1-1$ 个一定来自 $x$ 的原序列，填坑的方案数为 $C_{p3-1}^{p1-1}$
    右边有 $s{z}_x+s{z}_y-p3$ 个点，有 $s{z}_x-p1$ 个点一定来自 $x$ 的原序列，填坑的方案数为 $C_{s{z}_x+s{z}_y-p3}^{s{z}_x-p1}$
    $dp[x][p3]+=C_{p3-1}^{p1-1}\times C_{s{z}_x+s{z}_y-p3}^{s{z}_x-p1}\times dp[x][p1]\times dp[y][p2]$
    转移是$n^3$的，代码如下：

for p1 in [1,sz_x]
    for p2 in [1,sz_y]
        for p3 in [p1,p1+p2-1]

    $p2$ 在转移式中只出现了一次，因此调换顺序后：

for p1 in [1,sz_x]
    for p3 in [p1,p1+sz_y-1]
        for p2 in [p3-p1+1,sz_y]

    前缀和优化即可，时间复杂度降为 $n^2$

    若 $x$ 的拓扑序在 $y$ 之后，则 $p3>p4$
    $p1+p2\le p3\le p1+szx$，原来的转移式如下：

for p1 in [1,sz_x]
    for p2 in [1,sz_y]
        for p3 in [p1+p2,p1+sz_x]

    调换顺序后如下：

for p1 in [1,sz_x]
    for p3 in [p1+1,p1+sz_x]
        for p2 in [1,p3-p1]

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <int,int>;
const int maxn = 1e3 + 5;
const ll mod = 1e9 + 7;
int T, n, a[maxn][maxn], sz[maxn];
ll dp[maxn][maxn], C[maxn][maxn];
ll f[maxn], sum[maxn][maxn];
vector <int> g[maxn];

void dfs(int u, int fa) {
	sz[u] = 1, dp[u][1] = 1;
	for(auto v : g[u]) {
		if(sz[v]) continue;
		dfs(v, u);
		for(int i=1; i<=sz[u]; i++) f[i] = dp[u][i];
		memset(dp[u], 0, sizeof(dp[u]));
		for(int i=1; i<=sz[v]; i++) sum[v][i] = (sum[v][i-1] + dp[v][i]) % mod;
		if(a[u][v])
			for(int i=1; i<=sz[u]; i++)
				for(int k=i; k<=i+sz[v]-1; k++)
//					for(int j=k-i+1; j<=sz[v]; j++)
					(dp[u][k] += C[k-1][i-1] * C[sz[u]+sz[v]-k][sz[u]-i] % mod * f[i]\
					 % mod * (sum[v][sz[v]] - sum[v][k-i] + mod) % mod) %= mod;
		else 
			for(int i=1; i<=sz[u]; i++)
				for(int k=i+1; k<=i+sz[v]; k++)
//					for(int j=1; j<=k-i; j++)
					(dp[u][k] += C[k-1][i-1] * C[sz[u]+sz[v]-k][sz[u]-i] % mod * f[i]\
					 % mod * sum[v][k-i] % mod) %= mod;
		sz[u] += sz[v];
	}
}

int main() {
	for(int i=0; i<=1e3; i++) C[i][0] = 1;
	for(int i=1; i<=1e3; i++)
		for(int j=1; j<=i; j++)
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
	scanf("%d", &T);
	while(T--) {
		char str;
		scanf("%d", &n);
		memset(a, 0, sizeof(a));
		memset(sz, 0, sizeof(sz));
		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=n; i++) g[i].clear();
		for(int i=1, x, y; i<n; i++) {
			scanf("%d %c %d", &x, &str, &y);
			x++, y++;
			if(str == '<') a[x][y] = 1;
			else a[y][x] = 1;
			g[x].push_back(y);
			g[y].push_back(x);
		}
		dfs(1, 0);
		ll ans = 0;
		for(int i=1; i<=n; i++) ans = (ans + dp[1][i]) % mod;
		printf("%lld\n", ans);
	}
}