Permanent

2000ms

524288K

Description:

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 (10⁹ + 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 ≤ 10⁵; 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 ≤ 10⁹). 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 (10⁹ + 7).

Sample Input:

3 1
1 1 2

Sample Output:

Sample 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

Sample Output:

233333333

Informação

Provedor Codeforces

Código CF468E