GCD Sum

All submissions for this problem are available.
Read problems statements in Hindi, Mandarin chinese , Russian and Vietnamese as well.
You are given $n$ sequences $a_1, a_2, \dots, a_n$. Each of these sequences contains $m$ integers; let's denote the $j$th element of the $i$th sequence by $a_{i,j}$. Chef must perform the following operation exactly once:  choose an integer $k$ ($2 \le k \le n$)  choose $k$ **increasing** valid indices of sequences $1 \leq i_1 < i_2 < \dots < i_k \leq n$  choose $k$ arbitrary valid indices of elements $1 \leq j_1, j_2, \dots, j_k \leq m$  calculate $G = gcd(a_{i_1, j_1}, a_{i_2, j_2}, \dots, a_{i_k, j_k})$ Chef considered all possible ways to perform this operation, computed the number $G$ for each of them and calculated the sum of all these numbers modulo $10^9+7$. Can you find this sum? ### Input  The first line of the input contains two spaceseparated integers $n$ and $m$.  $n$ lines follow. For each $i$ ($1 \le i \le n$), the $i$th of these lines contains $m$ spaceseparated integers $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ denoting the $i$th sequence. ### Output Print a single line containing one integer — the sum of all possible results modulo $10^9 + 7$. ### Constraints  $2 \le n \le 20$  $1 \le m \le 10^5$  $1 \le a_{i, j} \le 10^5$ for each valid $i, j$ ### Subtasks **Subtask #1 (5 points):**  $2 \le n \le 10$  $1 \le m \le 5$ **Subtask #2 (15 points):**  $n = 2$  each sequence is a permutation of the numbers $\{1, 2, \dots, m\}$ **Subtask #3 (20 points):**  $n = 3$  each sequence is a permutation of the numbers $\{1, 2, \dots, m\}$ **Subtask #4 (60 points):** original constraints ### Example Input ``` 2 3 5 15 8 3 12 10 ``` ### Example Output ``` 25 ``` ### Explanation The answer is $gcd(5, 3) + gcd(5, 12) + gcd(5, 10) + gcd(15, 3) + gcd(15, 12) + gcd(15, 10) + gcd(8, 3) + gcd(8, 12) + gcd(8, 10) = 1 + 1 + 5 + 3 + 3 + 5 + 1 + 4 + 2 = 25$.Author:  fekete 
Editorial  https://discuss.codechef.com/problems/GCDSUM 
Tags  counting, easymedium, fekete, fekete, gcd, inclusnexclusn, likecs, ltime62 
Date Added:  25072018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 