$$pls(f_{u,i+j},f_{u,i}\cdot f_{v,k}\cdot C_{i+j-1}^{j}\cdot C_{sz_u+sz_v-i-j}^{sz_v-j})$$

for i=1 to sz[u]
for j=1 to sz[v]
for k=1 to j
pls(f[u][i+j],f[u][i]*f[v][k]*C[i+j-1][j]*C[sz[u]+sz[v]-i-j][sz[v]-j])


Code:

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e3+9;
const int mod=1e9+7;

int head[N],cnt;
struct Edge{int nxt,to,val;}G[N<<1];
int C[N][N],f[N][N],pre[N][N],suf[N][N],sz[N],g[N];

void add(int u,int v,int w) {
G[++cnt]=(Edge){head[u],v,w},head[u]=cnt;
G[++cnt]=(Edge){head[v],u,w^1},head[v]=cnt;
}

namespace OI {
void pls(int&x,int y) {x+=y;if(x>=mod)x-=mod;}
template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}
}using namespace OI;

void dfs(int u,int fa) {
sz[u]=f[u][1]=1;
for(int l=head[u];l;l=G[l].nxt) {
int v=G[l].to,w=G[l].val;
if(v==fa) continue;
dfs(v,u);
memset(g,0,sizeof(g));
if(w) {
for(int i=1;i<=sz[u];++i)
for(int j=1;j<=sz[v];++j)
pls(g[i+j],1ll*f[u][i]*pre[v][j]%mod*C[i+j-1][j]%mod
*C[sz[u]+sz[v]-i-j][sz[v]-j]%mod);
} else {
for(int i=1;i<=sz[u];++i)
for(int j=0;j<=sz[v];++j)
pls(g[i+j],1ll*f[u][i]*suf[v][j+1]%mod*C[i+j-1][j]%mod
*C[sz[u]+sz[v]-i-j][sz[v]-j]%mod);
}
sz[u]+=sz[v];
memcpy(f[u],g,sizeof(g));
}
pre[u][0]=suf[u][sz[u]+1]=0;
for(int i=1;i<=sz[u];++i) pre[u][i]=(pre[u][i-1]+f[u][i])%mod;
for(int i=sz[u];i>=1;--i) suf[u][i]=(suf[u][i+1]+f[u][i])%mod;
}

int solve() {
memset(head,0,sizeof(head)),cnt=0;
memset(f,0,sizeof(f));
int n;IN(n);
for(int i=1;i<n;++i) {
int u,v;char sign;
IN(u),sign=getchar(),IN(v);
add(u+1,v+1,sign=='<'?0:1);
}
dfs(1,0);
int ans=0;
for(int i=1;i<=n;++i) pls(ans,f[1][i]);
return ans;
}

int main() {
/*预处理组合数*/
for(int i=0;i<=N-2;++i) C[i][0]=1;
for(int i=1;i<=N-2;++i)
for(int j=1;j<=N-2;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
int T;IN(T);
while(T--) printf("%d\n",solve());
return 0;
}


QAQ