Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

E. Permanent
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Little X has solved the #P-complete problem in polynomial time recently. So he gives this task to you.

There is a special n × n matrix A, you should calculate its permanent modulo 1000000007 (109 + 7). The special property of matrix A is almost all its elements equal to 1. Only k elements have specified value.

You can find the definition of permanent at the link: https://en.wikipedia.org/wiki/Permanent

Input

The first line contains two space-separated integers n, k (1 ≤ n ≤ 105; 1 ≤ k ≤ 50).

The next k lines contain the description of the matrix. The i-th line contains three space-separated integers x i, y i, w i (1 ≤ x i,  y i ≤  n; 0  ≤  w i  ≤ 109). These numbers denote that A x i, y i = w i. All the elements of the matrix except of the given elements are equal to 1.

It's guaranteed that all the positions (x i, y i) are distinct.

Output

Print the permanent of the matrix modulo 1000000007 (109  +  7).

Examples
Input
3 11 1 2
Output
8
Input
10 103 3 3670567946 2 1245612731 3 467181466 9 41591686910 5 9859683363 1 5267922651 4 38635705810 4 3493041872 7 1020324993 6 502679075
Output
233333333