You are given n × m table. Each cell of the table is colored white or black. Find the number of non-empty sets of cells such that:

  All cells in a set have the same color.  Every two cells in a set share row or column. 


-----Input-----

The first line of input contains integers n and m (1 ≤ n, m ≤ 50) — the number of rows and the number of columns correspondingly.

The next n lines of input contain descriptions of rows. There are m integers, separated by spaces, in each line. The number equals 0 if the corresponding cell is colored white and equals 1 if the corresponding cell is colored black.


-----Output-----

Output single integer  — the number of non-empty sets from the problem description.


-----Examples-----
Input
1 1
0

Output
1

Input
2 3
1 0 1
0 1 0

Output
8



-----Note-----

In the second example, there are six one-element sets. Additionally, there are two two-element sets, the first one consists of the first and the third cells of the first row, the second one consists of the first and the third cells of the second row. To sum up, there are 8 sets.

Difficulty: interview

Starter code:

Solutions:
read = lambda: map(int, input().split())
n, m = read()
a = [list(read()) for i in range(n)]
ans = n * m
for i in range(n):
    cnt0 = a[i].count(0)
    cnt1 = a[i].count(1)
    if cnt0 > 1: ans += (2 ** cnt0 - cnt0 - 1)
    if cnt1 > 1: ans += (2 ** cnt1 - cnt1 - 1)
for i in range(m):
    cnt0 = sum(a[j][i] == 0 for j in range(n))
    cnt1 = sum(a[j][i] == 1 for j in range(n))
    if cnt0 > 1: ans += (2 ** cnt0 - cnt0 - 1)
    if cnt1 > 1: ans += (2 ** cnt1 - cnt1 - 1)
print(ans)

n, m = list(map(int, input().split()))
arr = [[0 for i in range(m)] for i in range(n)]
for i in range(n):
	arr[i] = list(map(int, input().split()))
ans = n * m
for i in range(n):
	c0 = 0
	c1 = 0
	for j in range(m):
		if arr[i][j] == 1:
			c1 += 1
		else:
			c0 += 1
	ans += max(0, 2 ** (c1) - c1 - 1)
	ans += max(0, 2 ** (c0) - c0 - 1)
for i in range(m):
	c0 = 0
	c1 = 0
	for j in range(n):
		if arr[j][i] == 1:
			c1 += 1
		else:
			c0 += 1
	ans += max(0, 2 ** (c1) - c1 - 1)
	ans += max(0, 2 ** (c0) - c0 - 1)
print(ans)

n, m = list(map(int, input().split()))
tbl = [list(map(int, input().split())) for _ in range(n)]

ans = 0
for i in range(n):
    c0 = 0
    c1 = 0
    for j in range(m):
        if tbl[i][j] == 0:
            c0 += 1
        else:
            c1 += 1
    ans += 2**c0 - 1
    ans += 2**c1 - 1
for i in range(m):
    c0 = 0
    c1 = 0
    for j in range(n):
        if tbl[j][i] == 0:
            c0 += 1
        else:
            c1 += 1
    ans += 2**c0 - 1
    ans += 2**c1 - 1
ans -= n * m
print(ans)


3

n, m = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for j in range(n)]
s = n * m
for i in range(n):
	black = sum(a[i])
	if black > 1:
		s += 2 ** black - black - 1
	white = m - black
	if white > 1:
		s += 2 ** white - white - 1

b = [[a[i][j] for i in range(n)] for j in range(m)]
for i in range(m):
	black = sum(b[i])
	if black > 1:
		s += 2 ** black - black - 1
	white = n - black
	if white > 1:
		s += 2 ** white - white - 1

print(s)

n, m = list(map(int, input().split()))
d = [list(map(int, input().split())) for i in range(n)]

ans = 0
for p in d:
    x = sum(p)
    ans += pow(2, x) + pow(2, m - x) - 2 - m

for i in range(m):
    x = sum(d[j][i] for j in range(n))
    ans += pow(2, x) + pow(2, n - x) - 2

print(ans)


def sol():
	rows, cols = map(int, input().split())
	tab = [list(map(int, input().split())) for _ in range(rows)]
	res = rows * cols
	for row in range(rows):
		white = 0
		black = 0
		for col in range(cols):
			if tab[row][col] == 0:
				white += 1
			else:
				black += 1
		if white > 0:
			res += pow(2, white) - white - 1
		if black > 0:
			res += pow(2, black) - black - 1
	for col in range(cols):
		white = 0
		black = 0
		for row in range(rows):
			if tab[row][col] == 0:
				white += 1
			else: 
				black += 1
		if white > 0:
			res += pow(2, white) - white - 1
		if black > 0:
			res += pow(2, black) - black - 1
	print(res)
sol()

n,m = map(int, input().split())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
    
ans = 0
for i in range(n):
    l = sum([1 for e in a[i] if e == 0])
    nl = m - l
    ans += (2**l - 1 - l) + (2**nl - 1 - nl)

for i in range(m):
    l = 0
    for j in range(n):
        if a[j][i] == 0:
            l += 1
    nl = n - l
    ans += (2**l - 1 - l) + (2**nl - 1 - nl)
    
print(ans + n*m)

n,m=list(map(int,input().split()))
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
ans=0
for i in range(n):
    r=l[i]
    c1=r.count(1)
    c2=r.count(0)
    ans+=(((2**c1)-1)+((2**c2)-1))
for i in range(m):
    ls=[]
    for j in range(n):
        ls.append(l[j][i])
    c1=ls.count(1)
    c2=ls.count(0)
    ans+=(((2**c1)-1)+((2**c2)-1)-c1-c2)
print(ans)


n,m=list(map(int,input().split()))
rc=[]
cc=[]
cols=[[] for i in range(m)]
for i in range(n):
    a=list(map(int,input().split()))
    for i in range(len(a)):
        cols[i].append(a[i])
    rc.append([a.count(1),a.count(0)])
for i in cols:
    cc.append([i.count(1),i.count(0)])

total=0
for i in rc:
    total+=(2**i[0])-1+(2**i[1])-1
for i in cc:
    total+=(2**i[0]-1-i[0])+(2**i[1]-1-i[1])
print(total)
                


n,m = map(int,input().split())

grid = [None]*n

for i in range(n):
  grid[i] = list(map(int, input().split()))

result = 0

for i in range(n):
  t = sum(grid[i])
  result += 2**t + 2**(m-t)

for i in range(m):
  t = sum(grid[j][i] for j in range(n))
  result += 2**t + 2**(n-t)

result -= 2*(n+m) + n*m

print(result)

from sys import stdin, stdout
import random


n,m = list(map(int,stdin.readline().rstrip().split()))
table = []
for _ in range(n):
    table.append(list(map(int,stdin.readline().rstrip().split())))

table2 = [[0]*n for _ in range(m)]
for i in range(n):
    for j in range(m):
        table2[j][i] = table[i][j]

totalSets = 0
for i in range(n):
    if sum(table[i])>1:
        totalSets+=(2**sum(table[i]))-1-sum(table[i])
    if sum(table[i])<m-1:
        totalSets+=(2**(m-sum(table[i])))-1-(m-sum(table[i]))
    
for i in range(m):
    if sum(table2[i])>1:
        totalSets+=(2**sum(table2[i]))-1-sum(table2[i])
    if sum(table2[i])<n-1:
        totalSets+=(2**(n-sum(table2[i])))-1-(n-sum(table2[i]))

totalSets+=(n*m)

print(totalSets)


n, m = map(int, input().split())
mat = [list(map(int, input().split())) for i in range(n)]
ans = 0
for i in range(n):
    w = 0
    b = 0
    for j in range(m):
        if mat[i][j] == 1:
            w += 1
        else:
            b += 1
    ans += 2 ** w + 2 ** b - 2
for i in range(m):
    w = 0
    b = 0
    for j in range(n):
        if mat[j][i] == 1:
            w += 1
        else:
            b += 1
    ans += 2 ** w + 2 ** b - 2
print(ans - n * m)

n, m = map(int, input().split())
data = [[]for i in range(n)]
data2 = [[0] * n for i in range(m)]
for i in range(n):
    data[i] = list(map(int, input().split()))
a = 0
for i in range(m):
    for j in range(n):
        data2[i][j] = data[j][i]
for i in range(n):
    su = sum(data[i])
    if su != 0:
        a += 2 ** su - 1
    if m - su != 0:
        a += 2 ** (m - su) - 1


for i in range(m):
    su = sum(data2[i])
    if su != 0:
        a += 2 ** su - 1
    if n - su != 0:
        a += 2 ** (n - su) - 1

print(a - n * m)

n, m = list(map(int, input().split()))
A = [0] * n
for i in range(n):
    A[i] = list(map(int, input().split()))

res = 0
for i in range(n):
    sum1 = sum(A[i])
    sum2 = m - sum1
    res += 2 ** sum1 + 2 ** sum2 - 2
sum1 = 0
sum2 = 0
for j in range(m):
    for i in range(n):
        sum1 += A[i][j]
    sum2 = n - sum1
    res += 2 ** sum1 + 2 ** sum2 - sum1 - sum2 - 2
    sum1 = 0
    sum2 = 0
print(res)





n, m = [int(i) for i in input().split()]
row_one = [0 for i in range(n)]
column_one = [0 for i in range(m)]
for i in range(n):
    tmp = [int(j) for j in input().split()]
    row_one[i] = sum(tmp)
    for j in range(m):
        column_one[j] += tmp[j]
row_zero = [m - i for i in row_one]
column_zero = [n - i for i in column_one]
ans = 0
for i in row_zero:
    ans += (1 << i)
for i in column_zero:
    ans += (1 << i)
for i in row_one:
    ans += (1 << i)
for i in column_one:
    ans += (1 << i)
ans = ans - 2*(m+n) - m*n
print(ans)

n,m=map(int,input().split())
a=[]
b=[]
ans =0 
for i in range(n):   
    a.append(0)
for i in range(m):
    b.append(0)
for i in range(n):
    l=list(map(int,input().split()))
    for j in range(m):
        a[i]=a[i]+l[j]
        b[j]=b[j]+l[j]
for i in range(n):   
    ans=ans+2**a[i]-1+2**(m-a[i])-1
for i in range(m):
    ans=ans+2**b[i]-1+2**(n-b[i])-1
ans=ans-n*m
print(ans)

n,m = input().split()
n = int(n)
m = int(m)
cnt = 0
b = []
for i in range(n):
    a = [int(x) for x in input().split()]
    b.append(a)
    a = sum(a)
    cnt += (1<<a) + (1<<(m-a)) - 2
for i in range(m):
    x = 0
    for j in range(n):
        x = x + b[j][i]
    cnt = cnt + (1<<x) + (1<<(n-x)) - 2

cnt -= n*m
print(cnt)


n, m = list(map(int, input().split()))

mtx = []
for _ in range(n):
    mtx.append(list(map(int, input().split())))

res = 0
for i in range(n):
    a = sum(mtx[i])
    b = m - a
    if a >= 1:
        res += 2 ** a - 1
    if b >= 1:
        res += 2 ** b - 1

for j in range(m):
    a = sum(mtx[i][j] for i in range(n))
    b = n - a
    if a >= 1:
        res += 2 ** a - 1
    if b >= 1:
        res += 2 ** b - 1

res -= n * m
print(res)


n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
col = [[0, 0] for i in range(m)]
row = [[0, 0] for i in range(n)]
for i in range(n):
    summa = sum(a[i])
    row[i] = [summa, m - summa]

for i in range(m):
    summa = 0
    for j in range(n):
        summa += a[j][i]
    col[i] = [summa, n - summa]

res = 0
for i in row:
    res += (2 ** i[0]) + (2 ** i[1]) - 2

for i in col:
    res += (2 ** i[0]) + (2 ** i[1]) - 2

res -= n *m
print(res)

from math import factorial
def c(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))
    
n, m = map(int, input().split())
ans = 0
a = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
    c0, c1 = 0, 0
    for j in range(m):
        if a[i][j]:
            c1 += 1
        else:
            c0 += 1
    for j in range(1, c0 + 1):
        ans += c(c0, j)
    for j in range(1, c1 + 1):
        ans += c(c1, j)
for j in range(m):
    c0, c1 = 0, 0
    for i in range(n):
        if a[i][j]:
            c1 += 1
        else:
            c0 += 1
    for i in range(2, c0 + 1):
        ans += c(c0, i)
    for i in range(2, c1 + 1):
        ans += c(c1, i)
print(ans)

import sys
n, m = list(map(int, input().split()))
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
c1 = []
c2 = []
for i in range(n):
    c1.append(a[i].count(1))
for i in range(m):
    c = 0
    for j in range(n):
        if a[j][i] == 1:
            c+= 1
    c2.append(c)
s = 0
for i in c1:
    s +=2**i-2+2**(m-i)
for i in c2:
    s +=2**i-2+2**(n-i)
s -=n*m
print(s)


import math
split = lambda: list(map(int, input().split()))
a, b = split()
rows = [split() for x in range(a)]
columns = [[x[y] for x in rows] for y in range(b)]
def choose(p, q):
    n = 1
    for x in range(p - q + 1, p + 1):
        n *= x
    n //= math.factorial(q)
    return n
s = 0
for x in rows + columns:
    p, q = x.count(0), x.count(1)
    for y in range(1, p + 1):
        s += choose(p, y)
    for y in range(1, q + 1):
        s += choose(q, y)
s -= a * b
print(s)

def solution():
    ans = 0
    n, m = map(int, input().split())
    matrix = []
    for i in range(n):
        matrix.append([int(j) for j in input().split()])
        
    for i in range(n):
        count = 0
        for j in range(m):
            if matrix[i][j] == 1:
                count += 1
        ans += 2**count - 1
        count = m - count
        ans += 2**count - 1
    
    for j in range(m):
        count = 0
        for i in range(n):
            if matrix[i][j] == 1:
                    count += 1
        
        if count > 1:
            ans += 2**count - 1 - count
        
        count = n - count
        if count > 1:
            ans += 2**count - 1 - count
    print(ans)
    
solution()

from math import factorial

def count(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))

n, m = map(int, input().split())
table = []
for i in range(n):
    table.append(list(map(int, input().split())))
ans = 0
for i in range(n):
    c0 = table[i].count(0)
    c1 = table[i].count(1)
    for j in range(1, c0 + 1):
        ans += count(c0, j)
    for j in range(1, c1 + 1):
        ans += count(c1, j)
for j in range(m):
    c0 = 0
    c1 = 0
    for i in range(n):
        if table[i][j] == 0:
            c0 += 1
        else:
            c1 += 1
    for i in range(2, c0 + 1):
        ans += count(c0, i)
    for i in range(2, c1 + 1):
        ans += count(c1, i)
print(ans)

n, m = map(int, input().split())

a = [list(map(int, input().split())) for _ in range(n)]

s = 0

for l in a:
    k = sum(l)
    s += 2**k - 1
    s += 2**(m-k) - 1

for i in range(m):
    k = sum(l[i] for l in a)
    s += 2**k - 1 - k
    s += 2**(n-k) - 1 - (n-k)

print(s)