Problem: There is a directed graph G with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i is directed from x_i to y_i. Here, x_i < y_i holds. Also, there are no multiple edges in G.

Consider selecting a subset of the set of the M edges in G, and removing these edges from G to obtain another graph G'. There are 2^M different possible graphs as G'.

Alice and Bob play against each other in the following game played on G'. First, place two pieces on vertices 1 and 2, one on each. Then, starting from Alice, Alice and Bob alternately perform the following operation:

* Select an edge i such that there is a piece placed on vertex x_i, and move the piece to vertex y_i (if there are two pieces on vertex x_i, only move one). The two pieces are allowed to be placed on the same vertex.



The player loses when he/she becomes unable to perform the operation. We assume that both players play optimally.

Among the 2^M different possible graphs as G', how many lead to Alice's victory? Find the count modulo 10^9+7.

Constraints

* 2 ≤ N ≤ 15
* 1 ≤ M ≤ N(N-1)/2
* 1 ≤ x_i < y_i ≤ N
* All (x_i,\ y_i) are distinct.

Input

Input is given from Standard Input in the following format:


N M
x_1 y_1
x_2 y_2
:
x_M y_M


Output

Print the number of G' that lead to Alice's victory, modulo 10^9+7.

Examples

Input

2 1
1 2


Output

1


Input

3 3
1 2
1 3
2 3


Output

6


Input

4 2
1 3
2 4


Output

2


Input

5 10
2 4
3 4
2 5
2 3
1 2
3 5
1 3
1 5
4 5
1 4


Output

816

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define F(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define f(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;

bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
 int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}
const int mod=1e9+7;
int n,m;
struct node{
   int u,v;
}p[100005];
int dp[1<<16],g[1<<16],P[1<<16];
int main () {
#ifndef ONLINE_JUDGE
//file("at2390");
#endif
     n=read();
	 m=read();
	 F(i,1,m){
	   p[i].u=read();
	   p[i].v=read();
	    g[p[i].u]|=1<<(p[i].v-1);
	 }
	 dp[0]=1;
	 P[0]=1;
	 F(i,1,m){
	    P[i]=2ll*P[i-1]%mod;
	 }
	 F(s,1,(1<<n)-1){
	    if((s&1)==(s>>1&1)){
		for(int nxt=s;nxt;nxt=(nxt-1)&s){
		   if((nxt&1)==(nxt>>1&1)){
			   int cnt=1;
			   F(i,1,n){
			      if((s>>(i-1))&1){
				     if((nxt>>(i-1))&1){
					   cnt=(1ll*cnt*P[__builtin_popcount(g[i]&(s^nxt))]%mod);  
					 }
				   else cnt=1ll*cnt*(P[__builtin_popcount(g[i]&nxt)]-1)%mod;
				  }
			  }
		      dp[s]=(dp[s]+1ll*dp[s^nxt]*cnt%mod)%mod;
		   }
		}
	  }
	 }
	 printf("%d\n",(P[m]-dp[(1<<n)-1]+mod)%mod);
    return 0;
}