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 syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

int n,m;
vvi a;

string f(int x){
	string s(n,'0');
	for(int i=0;i<n;i++) if(x&1<<i) s[i]='1';
	return s;
}

int main(){
	cin>>n>>m;
	a=vvi(n,vi(n));
	for(int i=0;i<m;i++){
		int s,t;
		cin>>s>>t;
		a[s-1][t-1]++;
	}
	int S=1<<n;
	vl dp(S),two(n+1);
	two[0]=1;
	for(int i=1;i<=n;i++) two[i]=two[i-1]*2%mod;
	for(int i=0;i<S;i++) if((i&3)==3){
		int T=i;
		do{
			if(T&3){
				ll res=1;
				bool B=((T&3)==3?1:0);
				for(int j=0;j<n;j++) if(i&1<<j){
					int X=0,Y=0;
					for(int k=j+1;k<n;k++) if(i&1<<k&&a[j][k]){
						if(T&1<<k) X++;
						else Y++;
					}
					if(T&1<<j) (res*=(two[Y]-1)*(B?1:two[X])%mod)%=mod;
					else (res*=two[X])%=mod;
				}
				if(B) (res*=dp[T])%=mod;
				(dp[i]+=res)%=mod;
			}
			T=(T-1)&i;
		}while(T!=i);
	}
	cout<<dp[S-1]<<endl;
}