#include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<bitset>

 using namespace std;

 typedef long long ll;

 const int mod=1e9+;

 const int N=;

 int read()

 {

    int x=,f=;char ch=getchar();

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();

    return x*f;

 }

 int n,m,Max,pop[N],pow[N],sum_e[N],to_e[N],f[N],a,b,e[N],ie[N],u[N];

 int lowbit(int x){return x&(-x);}

 int main()

 {

     n=read();m=read();

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

     {

        a=read(),b=read();

         e[<<a-]|=<<b-,ie[<<b-]|=<<a-;

     }

    Max=<<n;pow[]=;

    for (int i=;i<Max;i++) pop[i]=pop[i>>]+(i&),pow[i]=(ll)pow[i-]*%mod;

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

    {

        int v=lowbit(i);int p=i^v;

       sum_e[i]=sum_e[i^v]+pop[e[v]&i]+pop[ie[v]&i];

         f[i]=pow[sum_e[i]];to_e[i]=;

       for (int j=p;j;j=(j-)&p)

            u[i]=((ll)u[i]-(ll)f[i^j]*u[j]%mod+mod)%mod;

        for (int j=i;j;j=(j-)&i)

       {

           int v=lowbit(i^j);to_e[j]=to_e[j|v]-pop[e[v]&(i^j)]+pop[ie[v]&j];

            f[i]=((ll)f[i]-(ll)pow[sum_e[i^j]+to_e[j]]*u[j]%mod+mod)%mod;

        }

        u[i]=((ll)u[i]+f[i])%mod;

     }

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

    return ;

 }