CF468E.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

小 X 最近在多项式时间内解决了 #P-完全问题，因此他将这个任务交给了你。

给定一个特殊的 $ n \times n $ 矩阵 $ A $，你需要计算其积和式（permanent）对 $ 1000000007 $（即 $ 10^9 + 7 $）取模的结果。该矩阵 $ A $ 的特殊性质在于：其几乎所有元素都等于 $ 1 $，仅有 $ k $ 个元素具有指定的值。

积和式的定义请参见链接：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.

第一行包含两个以空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 10^5$；$1 \leq k \leq 50$）。

接下来的 $k$ 行描述矩阵。第 $i$ 行包含三个以空格分隔的整数 $x_i$、$y_i$、$w_i$（$1 \leq x_i, y_i \leq n$；$0 \leq w_i \leq 10^9$）。这些数表示 $A_{x_i,y_i} = w_i$。矩阵中除给定元素外，其余所有元素均为 $1$。

保证所有位置 $(x_i, y_i)$ 互不相同。

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

输出该矩阵的积和式对 1000000007（$10^9 + 7$）取模的结果。