Read problems statements in Mandarin Chinese and Russian as well. 

In every contest there should be an easy problem about matrices. December Cook-Off is not an exception.

Given a matrix A which consists of n rows and m columns, and contains integer numbers.

Consider every possible vector v of m elements, such that every 1 ≤ v_{i} ≤ n.

Let value of the vector be product of all Av_{i}, i  (1 ≤ i ≤ m). You are to count the sum of values over all possible vectors v.

------  Input details ------ 

The first line contains two integers n and m — dimensions of the matrix. Then n lines of m integers follow. The j_{th} element of i_{th} line contains A_{i, j}.

------  Output details ------ 

Output single integer — the answer for the problem modulo 10^{7} + 7, i.e the smallest non-negative integer number r that answer - r is divisible by 10^{7} + 7.

------  Constraints ------ 

1 ≤ n ≤ 47 

1 ≤ m ≤ 38 

0 ≤ |A_{i, j}| ≤ 100 

----- Sample Input 1 ------ 
2 2
1 2
3 4
----- Sample Output 1 ------ 
24
----- explanation 1 ------ 
All possible vectors are {(1, 1), (1, 2), (2, 1), (2, 2)} value(1, 1) = A1, 1 * A1, 2 = 1 * 2 = 2value(1, 2) = A1, 1 * A2, 2 = 1 * 4 = 4value(2, 1) = A2, 1 * A1, 2 = 3 * 2 = 6value(2, 2) = A2, 1 * A2, 2 = 3 * 4 = 12answer = 2 + 4 + 6 + 12 = 24

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
mbase = 10000007
(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append([int(word) for word in input().split()])
prod = 1
for j in range(m):
	sum = 0
	for i in range(n):
		sum = (a[i][j] + sum) % mbase
	prod = prod * sum % mbase
if prod < 0:
	prod += mbase
print(prod)


def main():
	MOD = 10 ** 7 + 7
	(n, m) = [int(x) for x in input().split()]
	mat = []
	for row in range(n):
		r = [int(x) for x in input().split()]
		mat.append(r)
	dp = [[0 for j in range(m)] for i in range(n)]
	for j in range(m - 1, -1, -1):
		for i in range(n):
			if j == m - 1:
				dp[i][j] = mat[i][j]
			else:
				tmp = 0
				for k in range(n):
					tmp += dp[k][j + 1]
				dp[i][j] = mat[i][j] * tmp % MOD
	ans = 0
	for i in range(n):
		ans += dp[i][0]
	ans %= MOD
	print(ans)
main()


mo = 10 ** 7 + 7

def mod(val):
	if val >= 0:
		val = val % mo
	else:
		while val < 0:
			val += mo
		val = val % mo
	return val
temp = list(map(int, input().split()))
n = temp[0]
m = temp[1]
mat = []
for i in range(n):
	mat.append(list(map(int, input().split())))
ans = 1
for j in range(m):
	s = 0
	for i in range(n):
		s += mat[i][j]
	s = mod(s)
	ans = ans * s
	ans = mod(ans)
print(ans)


a = input().split()
c = []
g = 1
for i in range(int(a[0])):
	b = input().split()
	c = c + [b]
for j in range(int(a[1])):
	s = 0
	for i in range(len(c)):
		s = (s + int(c[i][j])) % 10000007
	g = g * s % 10000007
	g = (g + 10000007) % 10000007
print(g)


e = 10 ** 7 + 7
(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append(list(map(int, input().split())))
ans = 1
for j in range(m):
	c = 0
	for k in range(n):
		c += l[k][j]
	ans = ans * c % e
print(ans)


from sys import stdin, stdout
from math import ceil

def solve():
	(n, m) = map(int, stdin.readline().split())
	a = []
	c = [0] * m
	mod = 10 ** 7 + 7
	for i in range(n):
		b = list(map(int, stdin.readline().strip().split()))
		a.append(b)
		for j in range(m):
			c[j] += b[j]
	ans = 1
	for i in range(m):
		ans *= c[i]
		ans %= mod
	print(ans)
solve()