链接: https://cses.fi/problemset/task/3154

板块: Mathematics

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定 $n\cdot(m+1)$ 个系数 $a_{i,j}$ 和 $b_i$，它们构成如下 $n$ 个线性方程：

• $a_{1,1}x_1 + a_{1,2}x_2 + \dots + a_{1,m}x_m = b_1 \pmod {10^9 + 7}$
• $a_{2,1}x_1 + a_{2,2}x_2 + \dots + a_{2,m}x_m = b_2 \pmod {10^9 + 7}$
• $\dots$
• $a_{n,1}x_1 + a_{n,2}x_2 + \dots + a_{n,m}x_m = b_n \pmod {10^9 + 7}$

你的任务是找出任意一组满足给定方程的 $m$ 个整数 $x_1, x_2, \dots, x_m$。

输入

第一行包含两个整数 $n$ 和 $m$：分别表示方程数和变量数。

接下来的 $n$ 行每行包含 $m+1$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}, b_i$：表示第 $i$ 个方程的系数。

输出

输出 $m$ 个整数 $x_1, x_2,\dots, x_m$：表示满足方程的变量值。这些值还必须满足 $0 \le x_i < 10^9 + 7$。你可以输出任意一组合法解。如果无解，则只输出 $-1$。

数据范围

$1 \le n, m \le 500$ $0 \le a_{i,j}, b_i < 10^9 + 7$

样例输入

3 3
2 0 1 7
1 2 0 0
1 3 1 2

样例输出

2 1000000006 3