#include<bits/stdc++.h>

 using namespace std;

 const int N=(<<)+,mod=1e9+;

 typedef long long ll;

 int n,m,x,y,f[N],g[N],h[N],one[N],w[N],in[N],out[N];

 ll bin[N];

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;++i)

     {

         scanf("%d%d",&x,&y);

         out[<<x-]|=(<<y-);in[<<y-]|=(<<x-);

     }

     bin[]=;

     for(int i=;i<=m;++i)bin[i]=bin[i-]*%mod;

     for(int s=;s<<<n;s++)one[s]=+one[s^(s&-s)];

     for(int s=;s<<<n;s++){

         int p=s&-s,ns=s^p;

         for(int t=ns;t;t=(t-)&ns)

             g[s]=(g[s]-1ll*f[s^t]*g[t]%mod)%mod;

         h[s]=h[ns]+one[in[p]&ns]+one[out[p]&ns];//如何求一个诱导子图中边数

         f[s]=bin[h[s]];

         for(int t=s;t;t=(t-)&s){

             int p=(s^t)&-(s^t);

             if(t==s)w[t]=;

             else w[t]=w[t^p]-one[out[p]&(s^t)]+one[in[p]&t];//求两个点集间的边数

             f[s]=(f[s]-1ll*g[t]*bin[w[t]+h[s^t]]%mod)%mod;

         }

         if(f[s]<)f[s]+=mod;

         g[s]=(g[s]+f[s])%mod;

     }

     printf("%d",f[(<<n)-]);

     return ;

 }