小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