值得注意的是一般的DAG的拓扑序列数量是NP问题，所以不能直接入手
题目中给出的图可以看做是一个树形图，虽然方向比较迷。考虑使用树形图的性质
不妨任选一个点为根做树形DP，注意到数的位置与方案数相关，所以也要设在状态内。故设$f_{i,j}$表示对于$i$及$i$的子树所有点构成的拓扑序列，$i$排在第$j$位的方案数，通过一个儿子一个儿子地合并来转移。
对于当前计算的点$u$的某一个儿子$v$已经算完，正要和$u$合并。设$sz_u$表示$u$和$u$的已合并子树的点数之和，并设$u < v$，那么序列中$v$要在$u$的后面。
先枚举$u$在已合并序列中的位置$j$，然后枚举$v$的子树对应的拓扑序列中有$k$个放在$u$的前面，不难得到转移方程：(dp_{u,j+k} leftarrow dp_{u,j} imes C_{j-1+k}^k imes C_{sz_u + sz_v - j - k} ^ {sz_v - k} imes sumlimits_{i=k+1}^{sz_v} dp_{v,k})
如果$u>v$也是差不多的
前后缀和优化最后的$sum dp_{v,k}$并预处理组合数
关于复杂度，注意到每一次合并的复杂度为"已合并的儿子大小"( imes)"当前合并的儿子大小"，可以看作任意两个点只会在它们的LCA处产生$1$的复杂度，所以总复杂度是$O(n^2)$的。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
#include<cassert>
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
bool f = 0;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = 1;
c = getchar();
}
if(c == EOF)
exit(0);
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return f ? -a : a;
}
const int MOD = 1e9 + 7;
int N , cntEd;
struct Edge{
int end , upEd;
}Ed[2003];
int head[1007] , C[1007][1007] , dp[1007][1007] , sz[1007] , pre[1007][1007] , suf[1007][1007] , tmp[1007];
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
inline char getc(){
char c = getchar();
while(c == ' ' || c == '
' || c == '
')
c = getchar();
return c;
}
void init(){
C[0][0] = 1;
for(int i = 1 ; i <= 1000 ; ++i){
C[i][0] = 1;
for(int j = 1 ; j <= 1000 ; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
void dfs(int u , int p){
sz[u] = 1;
dp[u][1] = 1;
for(int i = head[u] ; i ; i = Ed[i].upEd)
if(Ed[i].end != p){
dfs(Ed[i].end , u);
int v = Ed[i].end;
sz[u] += sz[v];
memset(tmp , 0 , sizeof(tmp));
if(i & 1)
for(int j = sz[u] - sz[v] ; j ; --j)
for(int k = 0 ; k < sz[v] ; ++k)
tmp[j + k] = (tmp[j + k] + 1ll * dp[u][j] * suf[v][k + 1] % MOD * C[j + k - 1][k] % MOD * C[sz[u] - j - k][sz[v] - k]) % MOD;
else
for(int j = sz[u] - sz[v] ; j ; --j)
for(int k = 1 ; k <= sz[v] ; ++k)
tmp[j + k] = (tmp[j + k] + 1ll * dp[u][j] * pre[v][k] % MOD * C[j + k - 1][k] % MOD * C[sz[u] - j - k][sz[v] - k]) % MOD;
memcpy(dp[u] , tmp , sizeof(tmp));
}
for(int i = 1 ; i <= sz[u] ; ++i)
pre[u][i] = (pre[u][i - 1] + dp[u][i]) % MOD;
for(int i = sz[u] ; i ; --i)
suf[u][i] = (suf[u][i + 1] + dp[u][i]) % MOD;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
init();
for(int T = read() ; T ; --T){
N = read();
for(int i = 1 ; i < N ; ++i){
int a = read() + 1;
char c = getc();
int b = read() + 1;
if(c == '>')
swap(a , b);
addEd(a , b);
addEd(b , a);
}
dfs(1 , 0);
cout << pre[1][N] << endl;
memset(dp , 0 , sizeof(dp));
memset(pre , 0 , sizeof(pre));
memset(suf , 0 , sizeof(suf));
memset(head , 0 , sizeof(head));
cntEd = 0;
}
return 0;
}
=