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