Permanent

题意翻译

给定一个 $n\times n$ 的矩阵，初始时矩阵的每个元素都为 $1$。 又给出 $k$ 个三元组 $(x,y,z)$，表示将矩阵的 $(x,y)$ 位置变成 $z$。 你需要求出完成这些变换之后矩阵的积和式。对 $10^9+7$ 取模。 积和式的定义： $$ per(A)=\sum_{\pi}\prod_{i=1}^na_{i,\pi(i)} $$ 其中 $\pi$ 取遍全部 $1\sim n$ 共 $n!$ 个排列。

题目描述

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

输入输出格式

输入格式

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},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 (10^{9}+7) $ .

输入输出样例

输入样例 #1

3 1
1 1 2

输出样例 #1

8

输入样例 #2

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

输出样例 #2

233333333

题意翻译

给定一个 $n\times n$ 的矩阵，初始时矩阵的每个元素都为 $1$。 又给出 $k$ 个三元组 $(x,y,z)$，表示将矩阵的 $(x,y)$ 位置变成 $z$。 你需要求出完成这些变换之后矩阵的积和式。对 $10^9+7$ 取模。 积和式的定义： $$ per(A)=\sum_{\pi}\prod_{i=1}^na_{i,\pi(i)} $$ 其中 $\pi$ 取遍全部 $1\sim n$ 共 $n!$ 个排列。