题目传送门：https://agc016.contest.atcoder.jp/tasks/agc016_f
题目大意：
给定一个(N)点(M)边的DAG，(x_i)有边连向(y_i)，保证(x_i<y_i)，原图有(2^M)个生成子图，对于每个子图(G')，(A,B)两人正在玩一个游戏：初始时点1,2上有棋子，每次操作可以把某个棋子沿有向边移动一步，最后不能操作的人为输。问有多少个子图(G')满足先手必胜
这种神题一看就不会写……首先考虑博弈，先手必胜的话当且仅当(sg[1]!=sg[2])，这样不好求，我们考虑求(sg[1]=sg[2])的方案
考虑状压dp，记(f[S])表示只考虑(S)这个点集，使得(sg[1]=sg[2])的方案数
枚举(S)的一个子集(T)，其补集为(U)，假设(U)集合的(sg)值都为0，而(T)集合都不为0,，考虑转移：
(U)内部的边：一条都不能连
(U)到(T)的边：随便连
(T)到(U)的边：(T)中的点至少有一条出边
如何保证1,2的(sg)相同，保证他们在同一个集合里即可
至少连边和随意连边我们可以预处理出来，一次转移为(O(n))，所以总复杂度为(O(3^n*n))
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define lowbit(x) ((x)&-(x))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1; char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=15,p=1e9+7;
bool map[N+10][N+10];
int f[N+10][(1<<N)+10],g[N+10][(1<<N)+10];
int dp[(1<<N)+10],ID[(1<<N)+10];
int mlt(int a,int b){
int res=1;
for (;b;b>>=1,a=1ll*a*a%p) if (b&1) res=1ll*res*a%p;
return res;
}
int main(){
int n=read(),m=read();
for (int i=1;i<=n;i++) ID[1<<(i-1)]=i;
for (int i=1;i<=m;i++){
int x=read(),y=read();
map[x][y]=1;
}
for (int i=1;i<=n;i++)
for (int sta=1;sta<1<<n;sta++)
f[i][sta]=f[i][sta^lowbit(sta)]+map[i][ID[lowbit(sta)]];
for (int i=1;i<=n;i++){
for (int sta=1;sta<1<<n;sta++){
int k=ID[lowbit(sta)];
if (!map[i][k]) g[i][sta]=g[i][sta^lowbit(sta)];
else g[i][sta]=(2ll*g[i][sta^lowbit(sta)]%p+1)%p;
}
}
for (int sta=1;sta<1<<n;sta++){
dp[sta]=1;
for (int sub=(sta-1)&sta;sub;sub=(sub-1)&sta){
if ((sub&1)&&((sta^sub)&2)) continue;
if ((sub&2)&&((sta^sub)&1)) continue;
int res=1,tmp=0;
for (int i=1;i<=n;i++) if (sub&(1<<(i-1))) res=1ll*res*g[i][sta^sub]%p;
for (int i=1;i<=n;i++) if ((sta^sub)&(1<<(i-1))) tmp+=f[i][sub];
res=1ll*res*mlt(2,tmp)%p;
dp[sta]=(dp[sta]+1ll*res*dp[sub])%p;
}
}
printf("%d
",(mlt(2,m)-dp[(1<<n)-1]+p)%p);
return 0;
}