#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <complex>
using namespace std;

// begin insert defines
#define two(x) (1LL<<(x))
#define forE(elem,v)  for(__typeof__(v.begin()) _it = v.begin(); _it != v.end();++_it) for(int _once=1, _done=0; _once; (!_done) ? (_it=v.end(), --_it) :_it ) for(__typeof__(*_it) & elem = * _it; _once && !(_once=0); _done=1)
#define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i)

// end insert defines

const int N = 13, B = 1 << 13, M = 1007, L = 10;

vector<int> lnk[N];
int ls[B], f[L][B];

void madd(int &a, int b)
{
  a += b;
  if (a >= M) a -= M;
}

int dp(int lv, int s)
{
  if (lv >= 10) return !s;
  int &ret = f[lv][s];
  if (ret != -1) return ret;
  ret = 0;
  for (int subset = s; subset > 0; subset = (subset - 1) & s) {
    if (!(ls[subset] & (~s))) {
      madd(ret, dp(lv + 1, s ^ subset));
    }
  }
  madd(ret, dp(lv + 1, s));
  return ret;
}

int n, m;

int main(int argc, char *argv[])
{
  cin >> n >> m;
  Rep(i, n) lnk[i].clear();
  Rep(i, m) {
    int x, y;
    cin >> x >> y;
    lnk[x].push_back(y);
  }
  Rep(i, two(n)) {
    ls[i] = 0;
    Rep(j, n) if (two(j) & i) forE(v, lnk[j]) ls[i] |= two(v);
  }
  memset(f, -1, sizeof(f));
  cout << dp(0, two(n) - 1) << endl;
  return 0;
}

import java.util.*;
import static java.lang.Math.*;
import java.io.*;

public class Solution {
	static class Foo41 {
		final static int MOD = 1007;
		int N;
		int highLen;
		int lowLen;
		int[] topsort;
		int[] reverseTopsort;
		Graph highReverse;
		Graph lowReverse;
		Graph crossGraph;
		MultiArray[] dp;
		int res = 0;
		
		void main() {
			BufferedReader br = null;
			try {
				br = new BufferedReader(new InputStreamReader(System.in));
				String[] s = br.readLine().split("\\s");
				int N = Integer.parseInt(s[0]);
				int M = Integer.parseInt(s[1]);
				TreeSet<Integer>[] g = new TreeSet[N];
				for (int i = 0; i < N; i++)
					g[i] = new TreeSet<Integer>();
				for (int i = 1; i <= M; i++) {
					s = br.readLine().split("\\s");
					int x = Integer.parseInt(s[0]);
					int y = Integer.parseInt(s[1]);
					if (x != y)
						g[y].add(x);
				}
				Graph graph = new Graph();
				graph.n = N;
				graph.degree = new int[N];
				graph.graph = new int[N][N];
				for (int u = 0; u < N; u++) {
					for (int v : g[u]) {
						graph.graph[u][graph.degree[u]++] = v;
					}
				}
				//long t = System.currentTimeMillis();
				int res = foo(graph);
				//System.out.println(System.currentTimeMillis()-t);
				System.out.println(res);
			} catch (Exception e) {
				e.printStackTrace();
			} finally {
				try {
					br.close();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}
		
		int foo(Graph g) {
			g = new TarjanSCC().doit(g);
			topsort = topsort(g);
			N = topsort.length;
			highLen = (N+1)/2;
			lowLen = N - highLen;
			reverseTopsort = reverse(topsort);
			highReverse = highReverse(g);
			lowReverse = lowReverse(g);
			crossGraph = crossGraph(g);
			dp = new MultiArray[highLen+1];
			for (int i = 0; i <= highLen; i++) {
				dp[i] = new MultiArray(i);
			}
			for (int i = 1; i <= highLen; i++) {
				fillMultiArray(i);
			}
			int[] arr = new int[N];
			//int[] util = new int[N];
			sumAll(arr);
			return res;
		}
		void sumAll(int[] arr) {
			sumAll(arr, highLen);
		}
		
		void sumAll(int[] arr, int index) {
			if (index == N) {
				for (int i = 0; i < highLen; i++) {
					arr[i] = 0;
					int u = topsort[i];
					for (int j = 0; j < crossGraph.degree[u]; j++) {
						int v = crossGraph.graph[u][j];
						arr[i] = max(arr[i], arr[reverseTopsort[v]]);
					}
				}
				//System.out.println(Arrays.toString(Arrays.copyOfRange(arr, highLen, N)) + ": " + dp[highLen].get(arr, highLen));
				res = (res + dp[highLen].get(arr, highLen)) % MOD;
				return;
			}
			int ceiling = 9;
			int u = topsort[index];
			for (int j = 0; j < lowReverse.degree[u]; j++) {
				int v = lowReverse.graph[u][j];
				ceiling = min(ceiling, arr[reverseTopsort[v]]);
			}
			for (int i = ceiling; i >= 0; i--) {
				arr[index] = i;
				sumAll(arr, index+1);
			}
		}
		
		void fillMultiArray(int len) {
			int[] arr = new int[len];
			int[] util = new int[len];
			for (int i = 9; i >= 0; i--) {
				arr[len-1] = i;
				fill(arr, util, 0, len);
			}
		}
		
		void fill(int[] arr, int[] util, int index, int len) {
			if (index == len-1) {
				int res = 0;
				copyArray(arr, util, len);
				int u = topsort[len-1];
				for (int j = 0; j < highReverse.degree[u]; j++) {
					int v = highReverse.graph[u][j];
					util[reverseTopsort[v]] = max(util[reverseTopsort[v]], util[len-1]);
				}
				res = dp[len-1].get(util, len-1);
				if (util[len-1] < 9) {
					util[len-1]++;
					for (int j = 0; j < highReverse.degree[u]; j++) {
						int v = highReverse.graph[u][j];
						util[reverseTopsort[v]] = max(util[reverseTopsort[v]], util[len-1]);
					}
					res = (res + dp[len].get(util, len)) % MOD;
				}
				dp[len].set(arr, len, res);
				return;
			}
			for (int i = 9; i >= 0; i--) {
				arr[index] = i;
				fill(arr, util, index+1, len);
			}
		}
		
		void copyArray(int[] a, int[] b, int n) {
			for (int i = 0; i < n; i++)
				b[i] = a[i];
		}
		
		Graph highReverse(Graph g) {
			Graph graph = new Graph();
			int n = g.n;
			graph.n = n;
			graph.degree = new int[n];
			graph.graph = new int[n][n];
			for (int i = 0; i < highLen; i++) {
				int u = topsort[i];
				for (int j = 0; j < g.degree[u]; j++) {
					int v = g.graph[u][j];
					if (reverseTopsort[v] < highLen)
						graph.graph[v][graph.degree[v]++] = u;
				}
			}
			return graph;
		}
		
		Graph lowReverse(Graph g) {
			Graph graph = new Graph();
			int n = g.n;
			graph.n = n;
			graph.degree = new int[n];
			graph.graph = new int[n][n];
			for (int i = highLen; i < N; i++) {
				int u = topsort[i];
				for (int j = 0; j < g.degree[u]; j++) {
					int v = g.graph[u][j];
					if (reverseTopsort[v] >= highLen)
						graph.graph[v][graph.degree[v]++] = u;
				}
			}
			return graph;
		}
		
		Graph crossGraph(Graph g) {
			Graph graph = new Graph();
			int n = g.n;
			graph.n = n;
			graph.degree = new int[n];
			graph.graph = new int[n][n];
			for (int i = 0; i < highLen; i++) {
				int u = topsort[i];
				for (int j = 0; j < g.degree[u]; j++) {
					int v = g.graph[u][j];
					if (reverseTopsort[v] >= highLen)
						graph.graph[u][graph.degree[u]++] = v;
				}
			}
			return graph;
		}
		
		int[] reverse(int[] arr) {
			int n = arr.length;
			int[] res = new int[n];
			for (int i = 0; i < n; i++)
				res[arr[i]] = i;
			return res;
		}
		
		static class Graph {
			int n;
			int[][] graph;
			int[] degree;
		}
		int[] topsort(Graph g) {
			int n = g.n;
			int[] res = new int[n];
			int count = 0;
			Queue<Integer> queue = new ArrayDeque<Integer>();
			int[] indegree = new int[n];
			for (int u = 0; u < n; u++) {
				for (int j = 0; j < g.degree[u]; j++) {
					int v = g.graph[u][j];
					indegree[v]++;
				}
				
			}
			for (int u = 0; u < n; u++) {
				if (indegree[u] == 0)
					queue.add(u);
			}
			while (!queue.isEmpty()) {
				int u = queue.remove();
				res[count++] = u;
				for (int j = 0; j < g.degree[u]; j++) {
					int v = g.graph[u][j];
					if (--indegree[v] == 0)
						queue.add(v);
				}
			}
			return res;
		}
		
		
		
		static class MultiArray {
			final static int LEN = 10;
			int[] val;
			MultiArray[] array;
			public MultiArray(int m) {
				if (m == 0)
					return;
				if (m == 1) {
					val = new int[LEN];
					Arrays.fill(val, -1);
				} else {
					array = new MultiArray[LEN];
					for (int i = 0; i < LEN; i++)
						array[i] = new MultiArray(m-1);
				}
			}
			// the first n elem of arr are indexes
			int get(int[] arr, int n) {
				if (n == 0)
					return 1;
				return get(this, arr, 0, n);
			}
			int get(MultiArray m, int[] arr, int index, int n) {
				if (index == n-1) {
					return m.val[arr[index]];
				}
				return get(m.array[arr[index]], arr, index+1, n);
			}
			void set(int[] arr, int n, int val) {
				set(this, arr, 0, n, val);
			}
			void set(MultiArray m, int[] arr, int index, int n, int val) {
				if (index == n-1) {
					m.val[arr[index]] = val;
					return;
				}
				set(m.array[arr[index]], arr, index+1, n, val);
			}
		}
		static class TarjanSCC {
			int n;
			int ind;
			int[] index;
			int[] lowIndex;
			Deque<Integer> stack;
			boolean[] inStack;
			int comp;
			int[] component;
			Graph g;
			Graph doit(Graph g) {
				this.g = g;
				n = g.n;
				index = new int[n];
				Arrays.fill(index, -1);
				lowIndex = new int[n];
				stack = new LinkedList<Integer>();
				inStack = new boolean[n];
				component = new int[n];
				for (int u = 0; u < n; u++) {
					if (index[u] == -1)
						tarjan(u);
				}
				TreeSet<Integer>[] newGraph = new TreeSet[comp];
				for (int i = 0; i < comp; i++)
					newGraph[i] = new TreeSet<Integer>();
				for (int u = 0; u < n; u++) {
					for (int j = 0; j < g.degree[u]; j++) {
						int v = g.graph[u][j];
						if (component[u] != component[v])
							newGraph[component[u]].add(component[v]);
					}
				}
				Graph graph = new Graph();
				graph.n = comp;
				graph.degree = new int[n];
				graph.graph = new int[n][n];
				for (int u = 0; u < comp; u++) {
					for (int v : newGraph[u]) {
						graph.graph[u][graph.degree[u]++] = v;
					}
				}
				return graph;
			}
			void tarjan(int u) {
				index[u] = ind;
				lowIndex[u] = ind;
				ind++;
				stack.push(u);
				inStack[u] = true;
				for (int j = 0; j < g.degree[u]; j++) {
					int v = g.graph[u][j];
					if (index[v] == -1) {
						tarjan(v);
						lowIndex[u] = min(lowIndex[u], lowIndex[v]);
					} else if (inStack[v]) {
						lowIndex[u] = min(lowIndex[u], index[v]);
					}
				}
				if (index[u] == lowIndex[u]) {
					int w = 0;
					do {
						w = stack.pop();
						inStack[w] = false;
						component[w] = comp;
					} while (u != w);
					comp++;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Foo41 foo = new Foo41();
		foo.main();
	}
}
 

import sys

n = 6 # between 0-9
maxn = 10
reqs = [(0,1), (1,2)]
reqs3 = [(1,3), (1,2)]
reqs2 = [(1,3), (0,1), (2,4),(0,4), (2,5),(3,4),(0,2)]

## how many different assignments (modulo by 1007)

def match_reqs(acc_list, reqs):
    for a,b in reqs:
        if acc_list[a] > acc_list[b]:
            return False
    
        
    return True

def req(n, reqs, acc_list):
    print(n, reqs, acc_list)
    summ = 0
    if (n == 0):
        if match_reqs(acc_list, reqs):
            return 1
        else:
            return 0
    
    
    for i in range(maxn):
        summ += req(n-1, reqs, acc_list + [i])
         
#    return summ % 1007
    return summ


def req2(n, reqs):
    if (n == 0):
        assert(reqs == [])
        return list(map(lambda x: [x], range(maxn)))
    
    reqs1, reqs2 = split_reqs(reqs, n)
    
    solutions = []
    subsolutions = req2(n-1, reqs1)
    print(n, len(subsolutions))
    print("FUCK YOU")
    for i in range(maxn):
        solutions += filter_list(subsolutions, i, reqs2)
    
    return solutions

def req22(n, reqs):
    return len(req2(n - 1, reqs)) % 1007

def split_reqs(reqs, n):
    reqs1 = []
    reqs2 = []
    for a,b in reqs:
        if a == n or b == n:
            reqs2.append((a,b))
        else:
            reqs1.append((a,b))
    return reqs1, reqs2

def filter_list(solutions, newval, reqs):
    result = []
    for solution in solutions:
        if match_reqs(solution + [newval], reqs):
            result.append(solution + [newval])
    return result
    
from operator import mul
from functools import reduce

def rlen(r):
    a,b = r
    if a > b:
        return 0
    return b-a+1

def update_ranges(ranges, val, reqs):
    removed_var = len(ranges)
    updated = list(ranges)
    for a,b in reqs:
        if a == removed_var:
            x, y = updated[b]
            if val > x:
                updated[b] = (val, y)
        if b == removed_var:
            x, y = updated[a]
            if val < y:
                updated[a] = (x, val)
    return updated

    
memodict = {}    
def req3(ranges, reqs):
    if (reqs == []):
        return reduce(mul, map(rlen, ranges), 1)
    
    key = (tuple(ranges),tuple(reqs))
    if key in memodict:
        return memodict[key]
        
    
    summ = 0
    lastr = ranges[-1]
    rest = ranges[:-1]
    
    a,b = lastr
    unrelated, related = split_reqs(reqs, len(rest))
    
    for val in range(a,b+1):
        updated = update_ranges(rest, val, related)
        summ += req3(updated, unrelated)

    summ = summ % 1007       
    memodict[key] = summ
    return summ


def req33(n, reqs):
    return req3([(0, maxn-1)] * n, reqs) % 1007

#print(req(n, reqs2, []) % 1007)

def runcommand():
    req_list = []
    n,m = map(int, sys.stdin.readline().split())
    for _ in range(m):
        a,b = map(int, sys.stdin.readline().split())
        req_list.append((a,b))
        
    print(req33(n, req_list))

runcommand()

#print(req22(6, reqs2))
#print(req33(6, reqs2))

# Enter your code here. Read input from STDIN. Print output to STDOUT
#!/usr/bin/python

import itertools
import operator

def memo(f):
    save = {}
    def func(*args):
        if args in save:
            return save[args]
        ret = f(*args)
        save[args] = ret
        return ret
    return func


getnums = lambda: map(int, raw_input().strip().split())
n, m = getnums()
le = [ [ x == y for x in xrange(n) ] for y in xrange(n) ]
#print le
for x in xrange(m):
    a, b = getnums()
    le[a][b] = 1

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            le[i][j] |= le[i][k] & le[k][j]

#print le

@memo
def subsets(nums):
    if len(nums) == 0: return []
    a = 1<<nums[0]
    ret = [a]
    for x in subsets(nums[1:]):
        ret.append(x)
        ret.append(a|x)
    return ret

#print subsets((0,1,2))

@memo
def ok(mask, now):
    if mask & (1<<now): return False
    for x in xrange(n):
        if mask & (1 << x) and le[now][x]:
            return False
    return True

dst = (1 << n) - 1
#print bin(dst)
@memo
def f(mask, lastval):
    ret = 0
    if mask == dst: return 1
    candidates = tuple(x for x in xrange(n) if ok(mask, x))
    for x in subsets(candidates):
        #print 'chosen', bin(x)
        for val in xrange(lastval+1, 10):
            ret = (ret + f(mask | x, val)) % 1007
    #print bin(mask), lastval, ret
    return ret

print f(0, -1)

/* Enter your code here. Read input from STDIN. Print output to STDOUT */

#include <stdio.h>

long long v[100000],b[20][20],i,j,k,l,m,n,a[20000][16];
long long bin[100][100];

void makaj(long long ii, long long horna, long long ind)
{

while(ind<n && (ii&(1<<ind))==0) ind++;

if(ind ==n) 
  {
  //koncim
  long long jj,kk,ll;

  
  jj = (ii^horna);
  
  if(horna==0) return;
  
//  printf("ii=%lld horna=%lld jj=%lld\n",ii,horna,jj);
  
  if(v[horna]==0 || v[jj]==0) return;
  
  for(kk=0;kk<n;kk++)
   if((1<<kk)&horna)
    for(ll=0;ll<n;ll++)
     if(((1<<ll)&jj) && b[ll][kk]) return;
  
  
  for(kk=1;kk<=10;kk++)
      {
      a[ii][kk] += a[jj][kk-1];
//      printf("ii=%lld kk=%lld jj=%lld pridavam %lld\n",ii,kk,jj,a[jj][kk-1]);
      }

  return;
  }

makaj(ii, horna, ind+1);
makaj(ii, horna + (1<<ind), ind+1);


return ;
}

int main()
{

for(i=0;i<20;i++) bin[i][0] = bin[i][i] = 1;

for(i=1;i<=20;i++)
 for(j=1;j<i;j++) 
   bin[i][j] = bin[i-1][j-1] + bin[i-1][j];


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

while(m--) {scanf("%lld %lld",&i,&j);b[j][i]=1;}


for(m=0;m<n+2;m++)
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   if(b[i][j])
     for(k=0;k<n;k++) 
       if(b[j][k]) b[i][k] = 1;


/*
for(i=0;i<n;i++) 
 {
 printf("%lld:",i);
 for(j=0;j<n;j++) printf("%lld ",b[i][j]);
 printf("\n");
 }
*/
for(i=0;i<(1<<n);i++)
 {
 v[i]=1;
 
 for(j=0;j<n;j++) 
  if(i&(1<<j))
   for(k=0;k<n;k++)
    if(i&(1<<k))
     for(l=0;l<n;l++)
       if((i&(1<<l))==0 &&  b[j][l] && b[l][k]) {
                                                 //printf("%lld hmm\n",i);
                                                 v[i]=0;
                                                 }
        
// if(v[i]) printf("%lld\n",i);
 }

a[0][0]=1;

for(i=1;i<(1<<n);i++)
//for(i=1;i<=2;i++)
 if(v[i])
  {
//  j=0;/
//  while(((1<<j)&i)==0) j++;
  
//  printf("makaj %lld %lld=j %lld\n",i,j,1<<j);
  
    makaj(i,0,0);  
  }

m=0;

//printf("bin %lld\n",bin[10][1]);

for(i=0;i<=10;i++) 
{
  m+=a[(1<<n)-1][i]*bin[10][i];
//  printf("%lld %lld\n",i, a[(1<<n)-1][i]*bin[10][i]);
}

//for(j=0;j<(1<<n);j++)
//for(i=0;i<=10;i++)
//  printf("%lld=i %lld=far pocet=%lld\n",j,i,a[(1<<n)-1][i]);


printf("%lld\n",m%1007);

return 0;
}