#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=1e9+7;
inline void inc(int &x,int y){x+=y;if (x>=p) x-=p;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
int ans=1;
for (;y;y>>=1,x=mul(x,x))
if (y&1) ans=mul(ans,x);
return ans;
}
int n,m,ans,go[20][20],a[16],bit[16];
int q[16][16],deg[16];
void init(ll S){for (int i=0;i<15;i++) a[i]=S&15,S>>=4;}
map<ll,int> M[20];
void work2(int v){
register char j;
register char cnt1[16],suf1[16];
memset(cnt1,0,16);suf1[15]=0;
for (j=0;j<deg[n-1];j++) cnt1[a[q[n-1][j]]]++;
for (j=14;j>=0;j--) suf1[j]=suf1[j+1]+cnt1[j];
register char cnt2[16],suf2[16];
memset(cnt2,0,16);suf2[15]=0;
for (j=0;j<deg[n-2];j++) cnt2[a[q[n-2][j]]]++;
for (j=14;j>=0;j--) suf2[j]=suf2[j+1]+cnt2[j];
register ll add=0;
for (j=0;v;j++){
add+=v*(1ll<<(suf1[j+1]+suf2[j+1]));
v=mul(v,bit[cnt1[j]]*bit[cnt2[j]]);
}
inc(ans,add%p);
}
void work1(int v){
static int cnt[20],suf[20];
int i=n-3;
for (int j=0;j<15;j++) cnt[j]=0;
for (int j=0;j<i;j++) if (go[i][j]) cnt[a[j]]++;
for (int j=15;j>=0;j--) suf[j]=suf[j+1]+cnt[j];
int lim=0;
while (cnt[lim]) lim++;
for (int j=0;j<=lim;j++){
a[i]=j;
work2(mul(v,1<<suf[j+1]));
v=mul(v,bit[cnt[j]]);
}
}
char cnt[20],suf[20];
int main()
{
for (int i=0;i<16;i++) bit[i]=(1<<i)-1;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
u=n-u;v=n-v;
go[u][v]=1;
if (v!=n-2) q[u][deg[u]++]=v;
}
M[0][0]=1;
for (int i=0;i<11;i++)
for (auto pr:M[i]){
register int v=pr.second;
register ll S=pr.first;
init(S);
register char j,lim=0;
for (j=0;j<12;j++) cnt[j]=0;
for (j=0;j<=i;j++) if (go[i+1][j]) cnt[a[j]]++;
for (j=11;j>=0;j--) suf[j]=suf[j+1]+cnt[j];
while (cnt[lim]) lim++;
for (int j=0,bit=(i+1)<<2;j<=lim;j++){
inc(M[i+1][(ll)j<<bit|S],mul(v,1<<suf[j+1]));
v=mul(v,(1<<cnt[j])-1);
}
}
if (n<=12){
for (auto pr:M[n-1]){
int v=pr.second;ll S=pr.first;
init(S);
if (a[n-1]!=a[n-2]) inc(ans,v);
}
printf("%d\n",ans);
}
else{
for (auto pr:M[n-4]) init(pr.first),work1(pr.second);
ans=(power(2,m)+p-ans)%p;
printf("%d\n",ans);
}
return 0;
}
./Main.cpp: In function ‘int main()’:
./Main.cpp:52:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
./Main.cpp:55:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
^