Sherlock And Large Numbers - II

0

0 votes
Medium, Modular arithmetic, Number Theory
Problem

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

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?