Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

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 xi, yi, wi (1 ≤ xi,  yi ≤  n; 0  ≤  wi  ≤ 109). These numbers denote that Axi, yi = wi. All the elements of the matrix except of the given elements are equal to 1.

It's guaranteed that all the positions (xi, yi) are distinct.

Output

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

Examples
Input
3 1
1 1 2
Output
8
Input
10 10
3 3 367056794
6 2 124561273
1 3 46718146
6 9 415916869
10 5 985968336
3 1 526792265
1 4 386357058
10 4 349304187
2 7 102032499
3 6 502679075
Output
233333333