← 返回题目列表

Codeforces · 468/E

E. 永久

中文机器翻译题面 查看原题

小X最近在多项式时间内解决了#P完全问题。所以他把这个任务交给了你。

有一个特殊的 n × n 矩阵 A,你应该计算它的永久模 1000000007 (109 + 7)。矩阵A的特殊性质是它的几乎所有元素都等于1。只有k个元素具有指定值。

您可以在链接中找到永久的定义:https://en.wikipedia.org/wiki/Permanent

输入

第一行包含两个以空格分隔的整数 n, k (1 ≤ n ≤ 105; 1 ≤ k ≤ 50)。

接下来的 k 行包含矩阵的描述。第 i 行包含三个以空格分隔的整数 xi、yi、wi (1 ≤ xi, yi ≤ n; 0 ≤ wi ≤ 109)。这些数字表示 Axi, yi = wi。矩阵中除给定元素之外的所有元素都等于 1。

保证所有位置 (xi, yi) 都是不同的。

输出

打印矩阵模 1000000007 (109 + 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