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:
/*
sg(1) ^ sg(2) != 0 不好考虑，正难则反，我们用 2^m - ( sg(1) = sg(2) 的方案数 )
考虑边集显然不现实，我们考虑点集

将 DAG 中的点按照 sg 值分层，显然点 1 和点 2 在同一层
根据分层，想到子集dp，f[S] 表示只考虑 S 这个点集使得 sg(1) = sg(2) 的方案数（注意 S 必须同时包含或不包含 1 和 2）

转移就枚举 S 的子集 T，设 U 为补集，其中 T 中 sg 值都不为 0，U 中 sg 值都为 0，也就是说 1 和 2 必须同时在 T 中或者 U 中
U 不能内部连边
T 内部就是 f[T]
T 中每个点都至少有一条到 U 的边（T 中 sg 值 += 1）
U 到 T 随便连
*/
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 20, M = (1 << 15) + 5, mod = 1e9 + 7;
typedef long long ll;
ll n, m;
ll ed[N], f[M], bit2[N * N] = {1};

int main() {
    cin >> n >> m;
    rep(i, 1, m) {
        bit2[i] = bit2[i - 1] * 2 % mod;
        int x, y; scanf("%d%d", &x, &y);
        ed[x - 1] |= (1 << (y - 1));
    }
    f[0] = 1;
    rep(S, 1, (1 << n) - 1) {
        if ((S & 1) == ((S >> 1) & 1)) {
            for (ll T = S; ; T = (T - 1) & S) {
                if ((T & 1) == ((T >> 1) & 1)) {
                    ll U = (S ^ T), cnt = 1;
                    rep(i, 0, n - 1) {
                        if ((S >> i) & 1) {
                            if ((T >> i) & 1)
                                cnt = cnt * (bit2[__builtin_popcount(ed[i] & U)] - 1) % mod;
                            else
                                cnt = cnt * bit2[__builtin_popcount(ed[i] & T)] % mod;
                        }
                    }
                    f[S] = (f[S] + cnt * f[T] % mod) % mod;
                }
                if (!T) break;
            }
        }
    }
    printf("%lld\n", (bit2[m] - f[(1 << n) - 1] + mod) % mod);
    return 0;
}