Permanent
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
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.
Print the permanent of the matrix modulo 1000000007 (109<=<=+<=<=7).
none