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^{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*_{*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^{9} + 7)$.
样例
3 1
1 1 2
8
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
233333333
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。