Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Permanent

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputLittle 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^{9} + 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^{5}; 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^{9}). These numbers denote that *A*_{xi, yi} = *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^{9} + 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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/20/2017 03:07:57 (p1).

Desktop version, switch to mobile version.

User lists

Name |
---|