CF468E Permanent

小 X 最近在多项式时间内解决了一个 $\#P$ 完全问题。于是他把这个任务交给了你。 给定一个特殊的 $n \times n$ 矩阵 $A$，请你计算它的 permanent，并对 $1000000007$（$10^9+7$）取模。矩阵 $A$ 的特殊性质是，几乎所有元素的值都是 $1$，只有 $k$ 个元素具有指定数值。 你可以在这里找到 permanent 的定义：https://en.wikipedia.org/wiki/Permanent

第一行包含两个用空格分隔的整数 $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$。除给定的 $k$ 个位置外，矩阵中其他所有元素均为 $1$。 保证所有 $(x_i, y_i)$ 位置互不相同。

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

由 ChatGPT 5 翻译