Moriarty has challenged Sherlock with another complicated maths problem. Moriarty found out that Sherlock is good with handling numbers represented in decimal form and so this time he changed the representation of numbers and gave Sherlock some large numbers represented as power of primes. Moriarty will give n large numbers to Sherlock. Moriarty has represented these number as power of first m prime numbers. This time, Moriarty wants Sherlock to multiply all these large numbers which will form a more larger number A. Moriarty wants to find the sum of all the distinct divisors of A. Since the sum will be extremely large, he wants the sum modulo 1000000007(1e9+7). Help Sherlock to win this challenge.
Note:- Use of fast I/O is recommended.
Note:- Python has not been allowed for this problem as python provides some features that hides the main motive for this problem. Sorry for the inconvenience.
See the sample case for better understanding.
Input format:
First line contains an integer T, denoting the number of test-cases.
The testcases will be given as follows:-
First line contains two integers n and m, representing the number of integers and the number of primes in which the number is represented.
Next n lines contain m integers (ai1, ai2, ..., aim) , where aij represents power of jth prime in ith number.
Output format:
For each testcase, print sum of all the distinct divisors of A modulo 1000000007(1e9 + 7).
Constraints:
1 <= T <= 10
1 <= m <= 100000(1e5)
1 <= n <= 100000(1e5)
1 <= n*m <= 100000(1e5)
0 <= aij <= 10^18
Subtasks:
Subtask #1 (15 points) : aij <= 10, m <= 1000
Subtask #2 (15 points) : aij <= 10, m <= 100000
Subtask #3 (20 points) : aij <= 10^9
Subtask #4 (50 points) : Original Constraints
In first testcase, only one number is given which is 2^1 and so A = 2. Now, 2 has two divisors 1 and 2 and so, sum of divisors = 1 + 2 = 3.
In second testcase, first number is 5^1, which is 5. Second number is (2^2) * (5^1), which is equal to 4 * 5 = 20.
Hence, A = product of all numbers = 20 * 5 = 100.
Now, divisors of 100 are :- 1, 2, 4, 5, 10, 20, 25, 50, 100.
Hence, sum of divisors = 1 + 2 + 4 + 5 + 10 + 20 + 25 + 50 + 100 = 217.