Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB

#2714. 波(b)

Statistics
【问题描述】

给定 $n$ 个 正整数序列 $a_1,a_2,...,a_n$ 每个序列长度为 $m$ 。 选择至少 $1$ 个序列,然后在每个被选择的序列中选择恰好一个元素,求出所有被选择的元素 的 gcd 。 求所有方案的结果之和,答案对 $10^9+7$ 取模。 两种方案不同,当且仅当存在至少一 个元素, 在一种方案中被选择,在另一种中没有。

【输入格式】

从文件 b.in 中读入数据。

第一行两个整数 $n,m$。

接下来 $n$ 行,每行 $m$ 个正整数,第 $i$ 行代表第 $i$ 个序列 $a_i$ 。

【输出格式】

输出到文件 b.out 中。

输出一个整数表示答案。

【样例输入输出】

Input

2 3
5 15 8
3 12 10

Output

78

样例2 请见下发文件。

【数据范围】

对于所有数据,有 $0\leq n \leq 20, 0\leq m \leq 10^5, 1 \leq a_{i,j}\leq 10^6$。

子任务编号 $n\leq$ $m\leq$ $a_{i,j}\leq$ 特殊性质 分值
1 $10$ $5$ $10^5$ 18
2 $7$ $20$ $10^5$ $a_{i,j}$ 在 $[1,10^5]$ 中随机生成 26
3 $1$ $10^5$ $10^5$ 1
4 $20$ $10^3$ $10^5$ 15
5 $20$ $10^5$ $2$ 10
6 $20$ $10^5$ $10^5$ $a_{i,j}$全部相同 10
7 $20$ $10^5$ $10^5$ 10
8 $20$ $10^5$ $10^6$ 10