统计每一行选择互质整数的方法数

题目描述

给定一个由正整数组成的 m x n 矩阵 mat。

返回一个整数，表示从矩阵的每一行中恰好选择一个整数，使得所有被选整数的最大公约数为 1 的选择方案数量。

由于答案可能非常大，请将其对 10^9 + 7 取模后返回。

输入

第一行包含两个整数 m 和 n，分别表示矩阵的行数和列数。

接下来 m 行，每行包含 n 个整数，表示矩阵中的元素。

输出

输出一个整数，表示满足条件的方案数对 10^9 + 7 取模的结果。

样例

提示

• 1 <= m, n <= 10^5
• 1 <= m * n <= 10^5
• 1 <= mat[i][j] <= 10^5

样例一解释：

第一行选择	第二行选择	最大公约数
1	3	1 ✅
1	4	1 ✅
2	3	1 ✅
2	4	2 ❌

其中 3 种组合的最大公约数为 1，因此答案是 3。

样例二解释：

所有组合的最大公约数都是 2，无法得到 1，因此答案是 0。

来源

leetcode