Problem Description

bobo has a permutation p₁,p₂,…,p_n of 1,2,…,n.

Knowing m extra constraints of form p_ai<p_bi, bobo wanna count the number of different permutations modulo (10⁹+7).

It is guaranteed that there is at least one such permutation.

Input

The input consists of several tests. For each tests:

The first line contains n,m (1≤n≤40,0≤m≤20). Each of the following m lines contain 2 integers a_i,b_i(1≤a_i,b_i≤n).

Output

For each tests:

A single number denotes the number of permutations.

3 1
1 2
3 2
1 2
2 3

3
1

Author

Xiaoxu Guo (ftiasch)