这题神坑啊……明明是你菜
首先大家都知道原题等价于给每个点分配一个$1$~$n$且两两不同的权值，同时还需要满足一些大于/小于关系的方案数。
先看一眼数据范围，既然写明了$n\le 1000$，那就应该是什么$O(n^2)$的做法了。显然这个东西只能是个DP，考虑到题中给出的是一个树形结构，那么就可以利用子树的相对独立性进行DP：设$f_{i,j}$表示以$i$为根的子树中有$j$个点的权值大于$i$的权值时的方案数，显然最终答案就是$\sum_{i}f_{root,i}$。
然后考虑怎么求出答案。通常树形DP都是自底向上逐个合并来得到每个点的DP值的，但注意这个DP无法做到像普通的树形DP一样可以快速(比如$O(1)$或者$O(\log^2 n)$之类)合并。不过这个DP还是可以比较高效地合并的，设要合并的两个子树大小分别为$n,m$，那么我们就可以通过枚举每一对$(i,j)$对应的$f_{\dots,i}$和$f_{\dots,j}$对合并后的DP数组的贡献来在$O(nm)$的时间内得到它们合并后的DP数组。
具体的合并过程就不写了，大体思路是先枚举最后$i$的权值在整个子树中的排名，然后枚举另一棵子树中有几个点权值比$i$的权值小，最后换元得到枚举$(i,j)$的形式。顺便一提，这个DP方程还需要一个前缀和优化才能做到$O(nm)$合并，还有大于和小于两种情况需要分开处理。
/**************************************************************
Problem: 3167
User: _Angel_
Language: C++
Result: Accepted
Time:3984 ms
Memory:8792 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=,p=;
int C[maxn][maxn];
struct DP{
int f[maxn],n;
void clear(){
memset(f,,sizeof(f));
n=;
f[]=;
}
DP &operator+=(const DP &b){
static int g[maxn];
memset(g,,sizeof(g));
for(int i=;i<n;i++)for(int j=,tmp=;j<=b.n;j++){
tmp=(tmp+b.f[j-])%p;
g[i+j]=(g[i+j]+(long long)f[i]*tmp%p*C[i+j][j]%p*C[n+b.n-i-j-][b.n-j]%p)%p;
}
memcpy(f,g,sizeof(f));
n+=b.n;
return *this;
}
DP &operator*=(const DP &b){
static int g[maxn];
memset(g,,sizeof(g));
int sum=;
for(int j=;j<b.n;j++)sum=(sum+b.f[j])%p;
for(int i=;i<n;i++)for(int j=,tmp=sum;j<b.n;j++){
g[i+j]=(g[i+j]+(long long)f[i]*tmp%p*C[i+j][j]%p*C[n+b.n-i-j-][b.n-j]%p)%p;
tmp=(tmp-b.f[j]+p)%p;
}
memcpy(f,g,sizeof(f));
n+=b.n;
return *this;
}
}f[maxn];
void dfs(int);
vector<int>G[maxn];
vector<bool>W[maxn];
int T,n,prt[maxn];
int main(){
C[][]=;
for(int i=;i<=;i++)for(int j=;j<=i;j++){
C[i][j]=C[i-][j];
if(j)C[i][j]=(C[i][j]+C[i-][j-])%p;
}
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(prt,,sizeof(prt));
for(int i=;i<=n;i++){
G[i].clear();
W[i].clear();
f[i].clear();
}
for(int i=,x,y;i<n;i++){
char c;
scanf("%d %c%d",&x,&c,&y);
x++;
y++;
G[x].push_back(y);
W[x].push_back(c=='>');
G[y].push_back(x);
W[y].push_back(c=='<');
}
dfs();
int ans=;
for(int i=;i<n;i++)ans=(ans+f[].f[i])%p;
printf("%d\n",ans);
}
return ;
}
void dfs(int x){
for(int i=;i<(int)G[x].size();i++)if(G[x][i]!=prt[x]){
prt[G[x][i]]=x;
dfs(G[x][i]);
if(W[x][i])f[x]+=f[G[x][i]];
else f[x]*=f[G[x][i]];
}
}