首先根据题目条件,题目中如果是=的点可以缩起来,然后\(a<b\)连边\(a\rightarrow b\),而且所有点入度为最多1,那么判掉有环的不合法情况,题目中的依赖关系就是一颗外向树森林,可以通过建一个另外的点向每棵树的根连边,能得到一颗外向树
然后就是dp,这里把打等号的一些相邻的数看成一个数,设\(f_{i,j}\)表示i点子树序列长度为j的方案,转移将儿子依次合并,即\(f_{x,l}\leftarrow f_{x,j}*f_{y,k}*g_{j,k,l}\)
上面的g是一个长度为j一个长度为k的序列合并成长度为l的序列方案数,转移枚举最后一个数是第一个序列的,第二个序列的或者是合并起来的
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register
using namespace std;
const int N=100+10,mod=1e9+7;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],hd[N],dg[N],tot=1;
il void add(int x,int y)
{
++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot,++dg[y];
}
int f[N][N],g[N][N][N<<1],d[N],sz[N];
void dp(int x)
{
sz[x]=f[x][0]=1;
for(int h=hd[x];h;h=nt[h])
{
int y=to[h];
dp(y);
memset(d,0,sizeof(d));
for(int i=0;i<sz[x];++i)
for(int j=1;j<=sz[y];++j)
for(int k=1;k<=i+j;++k)
d[k]=(d[k]+1ll*f[x][i]*f[y][j]%mod*g[i][j][k]%mod)%mod;
sz[x]+=sz[y];
memcpy(f[x],d,sizeof(d));
}
for(int i=sz[x];i;--i) f[x][i]=f[x][i-1];
f[x][0]=0;
}
int n,m,e[N][2],ff[N];
il int findf(int x){return ff[x]==x?x:ff[x]=findf(ff[x]);}
bool v[N];
bool check(int x)
{
if(v[x]) return 0;
v[x]=1;
for(int h=hd[x];h;h=nt[h]) if(!check(to[h])) return 0;
v[x]=0;
return 1;
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;++i) ff[i]=i;
for(int i=1;i<=m;++i)
{
int x=rd(),z=(getchar()=='<'),y=rd();
if(!z) --m,--i,ff[findf(x)]=findf(y);
else e[i][0]=x,e[i][1]=y;
}
for(int i=1;i<=m;++i) add(findf(e[i][0]),findf(e[i][1]));
for(int i=1;i<=n;++i)
if(findf(i)==i&&!check(i)) return puts("0"),0;
for(int i=1;i<=n;++i)
if(!dg[i]&&findf(i)==i) add(n+1,i);
g[0][0][0]=1;
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j)
for(int k=1;k<=i+j;++k)
{
if(i) g[i][j][k]=(g[i][j][k]+g[i-1][j][k-1])%mod;
if(j) g[i][j][k]=(g[i][j][k]+g[i][j-1][k-1])%mod;
if(i&&j) g[i][j][k]=(g[i][j][k]+g[i-1][j-1][k-1])%mod;
}
dp(n+1);
int ans=0,lim=1;
for(int i=1;i<=n;++i) lim+=findf(i)==i;
for(int i=1;i<=lim;++i) ans=(ans+f[n+1][i])%mod;
printf("%d\n",ans);
return 0;
}