正着做不好做，于是我们考虑反着来，如何计算一个点集s的答案呢，一定是所有的方案减去不合法的方案，不合法的方案一定是缩完点后是一个DAG，那么就一定有度数为0的scc，于是我们枚举s的子集，就是说这些点构成的scc的度数为0，这里我们就需要容斥了，容斥的目的是算出s集组成不合法的DAG的方案数，因为我们没有办法确定这里有几个scc。于是我们提前处理出g[s]表示这里面的每种不同scc的方案的贡献是$-1^{num-1}$，然后它们和其余的点之间随便连边，其余的点之间也随便连边，然后g数组我们是枚举任意一个点，然后枚举它所在的scc，然后在通过f数组转移，f就是总方案减去所有子集度数为0时的方案。
妙妙啊。
#include <cstdio>
#define N 16
#define mod 1000000007
using namespace std;
int n,m,to[<<N],cnt[<<N],bin[N*N],e[<<N];
int f[<<N],g[<<N];
int calc(int S,int T){
int ans=;
for(;S;S-=S&-S)
ans+=cnt[to[S&-S]&T];
return ans;
}
int main(){
scanf("%d%d",&n,&m);
bin[]=;
for(int i=;i<=m;i++)
bin[i]=bin[i-]*%mod;
for(int i=,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
to[<<u-]|=<<v-;
}
for(int i=;i<bin[n];i++)cnt[i]=cnt[i>>]+(i&);
for(int i=;i<bin[n];i++)e[i]=calc(i,i);
for(int i=;i<bin[n];i++){
int k=i&-i,s=i^k;
for(int j=(s-)&s;j;j=(j-)&s)
g[i]=(g[i]-1ll*g[i^j^k]*f[j|k]%mod+mod)%mod;
if(i^k)g[i]=(g[i]-g[i^k]+mod)%mod;
f[i]=bin[e[i]];
for(int j=i;j;j=(j-)&i)
f[i]=(f[i]-1ll*g[j]*bin[e[i^j]+calc(j,i^j)]%mod+mod)%mod;
(g[i]+=f[i])%=mod;
}
printf("%d\n",f[bin[n]-]);
return ;
}