Problem:
 Score : 300 points    Problem Statement We have a grid of H rows and W columns of squares. The color of the square at the i -th row from the top and the j -th column from the left (1 \leq i \leq H, 1 \leq j \leq W) is given to you as a character c_{i,j} : the square is white if c_{i,j} is . , and black if c_{i,j} is # .  Consider doing the following operation:   Choose some number of rows (possibly zero), and some number of columns (possibly zero). Then, paint red all squares in the chosen rows and all squares in the chosen columns.   You are given a positive integer K . How many choices of rows and columns result in exactly K black squares remaining after the operation? Here, we consider two choices different when there is a row or column chosen in only one of those choices.      Constraints  1 \leq H, W \leq 6  1 \leq K \leq HW  c_{i,j} is . or # .         Input Input is given from Standard Input in the following format:  H  W  K  c_{1,1}c_{1,2}...c_{1,W}  c_{2,1}c_{2,2}...c_{2,W}  :  c_{H,1}c_{H,2}...c_{H,W}       Output Print an integer representing the number of choices of rows and columns satisfying the condition.        Sample Input 1 2 3 2
..#
###      Sample Output 1 5  Five choices below satisfy the condition.   The 1 -st row and 1 -st column  The 1 -st row and 2 -nd column  The 1 -st row and 3 -rd column  The 1 -st and 2 -nd column  The 3 -rd column        Sample Input 2 2 3 4
..#
###      Sample Output 2 1  One choice, which is choosing nothing, satisfies the condition.       Sample Input 3 2 2 3
##
##      Sample Output 3 0       Sample Input 4 6 6 8
..##..
.#..#.
#....#
######
#....#
#....#      Sample Output 4 208

Solution (Python):
H,W, K = [int(v) for v in input().split()]
S = [list(input()) for _ in range(H)]

total = 0
for s in S:
    total += s.count("

ans = 0

def check(h_l,w_l):
    S_copy = []
    for s in S:
        S_copy.append(s[:])
    for h,b1 in enumerate(h_l):
        if b1: continue
        for i in range(W):
            S_copy[h][i] = 'r'

    for w,b1 in enumerate(w_l):
        if b1: continue
        for i in range(H):
            S_copy[i][w] = 'r'

    c = 0
    for s in S_copy:
        c += s.count("
    return c == K





def bit(N):
    r = []
    for i in range(2**N):
        ret = []
        for j in range(N):
            ret.append(i>>j & 1 == 1)
        r.append(ret)
    return r

H_L = bit(H)
W_L = bit(W)

ans = 0
for h_l in H_L:
    S_c = S[:]
    for w_l in W_L:
        if check(h_l,w_l):
            ans += 1
print(ans)

Solution (Python):
h,w,K=map(int,input().split())
clist=[input() for _ in range(h)]

counter = 0
for i in range(2**w):
    for j in range(2**h):
        read=[]
        for l in range(h):
            if j >> l & 1:
                read.append([True]*w)
            else:
                read.append([False]*w)
        for k in range(w):
            if i >> k & 1:
                for m in range(h):
                    read[m][k] = False
        tmpcounter=0
        for a in range(h):
            for b in range(w):
                if clist[a][b] == '
                    tmpcounter += 1
        if tmpcounter == K:
            counter += 1
print(counter)

Solution (Python):

H,W,K = map(int,input().split())
glid = [[] for i in range(H)]
for i in range(H):
    glid[i]=list(input())
import itertools
status = [(0, 1) for _ in range(H)]
h_state = list(itertools.product(*status))
status = [(0, 1) for _ in range(W)]
w_state = list(itertools.product(*status))
ans = 0
for h_case in h_state:
    for w_case in w_state:
        nglid = [[False]*W for _ in range(H)]
        for hidx,h in enumerate(h_case):
            for widx,w in enumerate(w_case):
                if h!=1:
                    nglid[hidx][widx] = True
                if w!=1:
                    nglid[hidx][widx] = True
        black = 0

        cnt=0
        for i in range(H):
            for j in range(W):
                if glid[i][j]=="
                    cnt+=1
        if cnt==K:
            ans+=1

print(ans)

Solution (Python):
import numpy as np
H,W,K = map(int,input().split())
grid = ""
for i in range(H):
    grid += input()

grid2 = []
for i in grid:
    if i == ".":
        grid2.append(1)
    else:
        grid2.append(0)
    
ans = 0
for i in range(2 ** (H+W)):
    X = np.array(grid2)
    X = X.reshape(H,W)
    pattern = []
    for j in range(H+W):
        if ((i >> j) & 1):
            pattern.append(j)
    
    h = []
    w = []
    
    for k in pattern:
        if k <= (H-1):
            h.append(k)
        else:
            k -= H
            w.append(k)
    X[h,:]=1
    X[:,w]=1
    if X.reshape(1,-1).tolist()[0].count(0) == K:
        ans += 1
        
print(ans)

Solution (Python):

h,w,K = map(int, input().split())
G = [list(input()) for _ in range(h)]
count = 0
for i in range(2**h):
    for j in range(2**w):
        tmp = 0
        for k in range(h):
            for m in range(w):
                if (not i>>k&1) and (not j>>m&1) and G[k][m] == '
                    tmp +=1
        if tmp == K:
            count += 1
print(count)

Solution (Python):
h,w,k = list(map(int, input().split() ) )
c = [ list(input()) for i in range(h) ]


newc = [[ 1 if ee == '

newc_t = list(map(list, zip(*newc)))

blackcnt = sum( [sum(i) for i in newc] )
need_del = blackcnt - k

cnt = 0

for hh in range(2 ** h):
  
  hh_del = list( map( int, list(format(hh,'0{}b'.format(h)) ) ))
  for ww in range(2 ** w):
    ww_del = list( map( int, list(format(ww,'0{}b'.format(w)) ) ))
    
    row_del_cnt = sum( [sum(row) for row,check in zip(newc,   hh_del) if check ==1] )
    col_del_cnt = sum( [sum(col) for col,check in zip(newc_t, ww_del) if check ==1] )
    
    
    d_cnt = 0
    for ri,rc in enumerate(hh_del):
      for ci,cc in enumerate(ww_del):
        d_cnt += newc[ri][ci] * rc * cc
    
    if need_del == row_del_cnt + col_del_cnt - d_cnt:
      cnt += 1
      
print(cnt)

Solution (Python):

"""
Created on Sun Jul  5 21:07:34 2020

@author: NEC-PCuser
"""
import copy

H, W, K = map(int, input().split())

c = []
c_count = 0
for i in range(H):
    c_li = list(input())
    c_count += c_li.count("
    c.append(c_li)
N = H + W
ans = 0
for i in range(2 ** N):
    count = c_count
    c_tmp = copy.deepcopy(c)
    for j in range(N):
        if ( j <  W and (i >> j) & 1):
            for k in range(H):
                if (c_tmp[k][j] == "
                    count -= 1
                c_tmp[k][j] = "!"
        elif ((i >> j) & 1):
            for k in range(W):
                if (c_tmp[j - W][k] == "
                    count -= 1
    if count == K:
        ans += 1

print(ans)

Solution (Python):
h,w,k= map(int,input().split())
mat=[]
for i in range(h):
  mat.append(input())
    
ans = 0    
for i in range(2**(h+w)):
  num = 0
  t = i
  tmat = [list(jj) for jj in mat]
  
  for j in range(h):
    if j>0:
      t = t>>1
    if t&1:
      tmat[j]=list(["9"]*w)
      
  for j in range(w):
    t = t>>1
    if t&1:
      for p in range(h):
        tmat[p][j]="9"
      
  for hh in range(h):
    for ww in range(w):
      if tmat[hh][ww]=="
        num+=1
      if num>k:
        break
        
  if num==k:
    ans +=1
    
print(ans)

Solution (Python):
import numpy as np
import copy
from itertools import product


H, W, K = map(int, input().split())
B = np.array([list(input().rstrip()) for _ in range(H)], str)
ans = 0

for h, w in product(range(2 ** H), range(2 ** W)):
    C = copy.deepcopy(B)
    for i in range(H):
        b = h >> i & 1
        if b:
            C[i, :] = '.'

    for i in range(W):
        b = w >> i & 1
        if b:
            C[:, i] = '.'

    ans += np.sum(C == '

print(ans)

Solution (Python):
import copy
H,W,K=map(int,input().split())
C=[]
for _ in range(H):
    c=list(input())
    C.append(c)
U=copy.deepcopy(C)
a=2**H
b=2**W
ans=0
for i in range (a):
    C=copy.deepcopy(U)
    for j in range(H):
        if ((i>>j)&1):
            C[j]=['a']*W
    E=copy.deepcopy(C)
    for h in range(b):
        C=copy.deepcopy(E)
        for k in range(W):
            if ((h>>k)&1):
                for q in range(H):
                    C[q][k]='a'
        count=0
        for d in range(H):
            for e in range(W):
                if C[d][e]=='
                    count+=1
        if count==K:
            ans+=1

print(ans)

Solution (Python):
from itertools import combinations
def main():
    h, w, k = list(map(int, input().split()))
    C = [list(input()) for _ in range(h)]
    Ch = []
    Cw = []
    for c in C:
        Ch.append(sum(i == '
    C = [list(x) for x in zip(*C)]
    for c in C:
        Cw.append(sum(i == '
    C = [list(x) for x in zip(*C)]
    tot = sum(Ch)
    ans = 0
    for i in range(h + 1):
        for j in range(w + 1):
            for ch in combinations(range(h), i):
                for cw in combinations(range(w), j):
                    ci = sum(Ch[ii] for ii in ch)
                    cj = sum(Cw[jj] for jj in cw)
                    dup = sum(C[ii][jj] == '
                    if tot - (ci + cj - dup) == k:
                        ans += 1
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
def powerset_generator(provided_set):
  if len(provided_set) > 0:
    for c in powerset_generator(provided_set[1:]):
      yield [provided_set[0]] + c
      yield c
  else:
    yield []

H, W, K = map(int, input().split())
masu = [list(input()) for _ in range(H)]

hw_list = ['h'+ str(i) for i in range(H)] + ['w'+ str(j) for j in range(W)]

res = 0
for red_list in powerset_generator(hw_list):
    red_h_list = []
    red_w_list = []
    for red in red_list:
        if red.startswith('h'):
            red_h_list.append(int(red[1:]))
        else:
            red_w_list.append(int(red[1:]))
    count = 0
    for i in range(H):
        if i in red_h_list:
            continue
        for j in range(W):
            if j in red_w_list:
                continue
            if masu[i][j] == '
                count += 1
    if K == count:
        res += 1

print(res)

Solution (Python):
from itertools import product
h,w,k = map(int,input().split())
c = [input() for _ in range(h)]
row = list(product(range(2), repeat=h))
col = list(product(range(2), repeat=w))
g = "
cl = []
for i in row:
  for j in col:
    s=""
    for k in range(h):
      for l in range(w):
        if i[k] != 0 and j[l] != 0:
          s += c[k][l]
    cl.append(s)

for i in range(len(cl)):
  cl[i] = cl[i].replace(".","")
  
print(cl.count(g))

Solution (Python):
h,w,K=map(int,input().split())
c=[input() for i in range(h)]
total=0
for i in range(h):
    for j in range(w):
        if c[i][j]=="
            total+=1

ans=0
l=[]
for bit in range(1<<h):
    bh=bin(bit)
    bh="0"*(h-len(bh[2:])) +bh[2:]
    gyo=[]
    for i in range(h):
        if bh[-i-1]=="1":
            gyo.append(i)
    for BIT in range(1<<w):
        bw=bin(BIT)
        bw="0"*(w-len(bw[2:]))+bw[2:]
        
        cl=[]
        for j in range(w):
            if bw[-j-1]=="1":
                cl.append(j)
        
        
        su=0
        for r in range(h):
            if r in gyo:
                continue
            for k in range(w):
                if k in cl:
                    continue
                if c[r][k]=="
                    su+=1
        
        if su==K:
            ans+=1
print(ans)

Solution (Python):
import numpy as np
from itertools import combinations

H,W,K = map(int, input().split())

grid = np.zeros([H,W],dtype=int)
for i in range(H):
  row = input().replace('.', '0').replace('
  for j in range(W):
  	grid[i,j]=int(row[j])

grid2 = grid.copy()
count = 0
for i in range(-1, H):
  for j in range(-1, W):
    if i != -1 and j != -1:
      for p in combinations(range(H), i+1):
      	for q in combinations(range(W), j+1):
          grid2[p, :] = 0
          grid2[:, q] = 0
          if grid2.sum() == K: 
            count += 1
            
          grid2 = grid.copy()
    
    elif i == -1 and j != -1:
      for q in combinations(range(W), j+1):
        grid2[:, q] = 0
        if grid2.sum() == K: 
          count += 1
          
        grid2 = grid.copy()
    
    elif i != -1 and j == -1:
      for p in combinations(range(H), i+1):
        grid2[p, :] = 0
        if grid2.sum() == K:
          count += 1
          
        grid2 = grid.copy()
    
    else:
      if grid2.sum() == K:
        count += 1
        
      grid2 = grid.copy()
          
print(count)

Solution (Python):
from copy import deepcopy
def bit_s(bit, n):
    l = []
    for i in range(n):
        if bit & (1 << i):
            l.append(i)
    return l
h, w, k = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0
c2 = deepcopy(c)
for bit in range(1 << h):
    l = bit_s(bit, h)
    for i in l[::-1]:
        del c2[i]
    for bit2 in range(1 << w):
        cnt = 0
        l2 = bit_s(bit2, w)
        for i in c2:
            for j in l2:
                if i[j] == "
                    cnt += 1
        if cnt == k:
            ans += 1
    c2 = deepcopy(c)
print(ans)

Solution (Python):
import copy
h, w, K  = map(int, input().split())
c = []
for i in range(h):
    r = list(input())
    c.append(r)

def count(A):
    ret = 0
    for r in A:
        ret += r.count("
    return ret
ans = 0

for bit in range(1<<(h+w)):
    tmp = copy.deepcopy(c)
    for j in range(h+w):
        if (bit&(1<<j)):
            
            
            if j < h:
                for k in range(w):
                    tmp[j][k] = "a"
            
            else:
                for k in range(h):
                    tmp[k][j-h] = "a"
    x = count(tmp)
    if count(tmp) == K:
        ans += 1
print(ans)

Solution (Python):
H,W,K = map(int,input().split())

c = []
for _ in range(H):
    c.append(input())

ans = 0
for i in range(2**(H+W)):
    list = [[0 for _ in range(W)] for _ in range(H)]
    for j in range(H+W):
        if (i >> j) % 2 == 0:
            if j < H:
                for k in range(W):
                    list[j][k] += 1 
            else:
                for k in range(H):
                    list[k][H-j] += 1 
    count_k = 0
    for h in range(H):
        for w in range(W):
            if list[h][w] == 0 and c[h][w] == "
                count_k += 1
    if count_k == K:
        ans += 1

print(ans)

Solution (Python):
h,w,k = map(int,input().split())
c_list=[input() for _ in range(h)]

def iter_p_adic(p, n):
    '''
    連続して増加するp進数をリストとして返す。nはリストの長さ
    return
    ----------
    所望のp進数リストを次々返してくれるiterator
    '''
    from itertools import product
    tmp = [range(p)] * n
    return product(*tmp)

h_iter = list(iter_p_adic(2, h))
w_iter = list(iter_p_adic(2, w))

count = 0
for h_iter_i in range(len(h_iter)):
    for w_iter_i in range(len(w_iter)):
        count_tmp = 0
        for h_i in range(len(c_list)):
            for w_i in range(len(c_list[h_i])):

                if c_list[h_i][w_i] == '
                    count_tmp += 1
        if count_tmp == k:
            count += 1

print(count)

Solution (Python):
import numpy as np

h, w, k = map(int, input().split())
c = np.array([list(input()) for _ in range(h)])
ans = 0
for i in range(2 ** (h+w)):
    cnt = 0
    c_ = c.copy()
    
    for j in range(h+w):
        if i >> j & 1:
            if j < h:
                c_[j] = 'x'
            else:
                c_.T[j-h] = 'x'
    for y in range(h):
        for x in range(w):
            if c_[y][x] == '
                cnt += 1
    if cnt == k:
        ans += 1
print(ans)

Solution (Python):




def main():
    H, W, K = map(int, input().split())
    field = []
    row = [0] * H
    column = [0] * W
    total = 0
    for _ in range(H):
        field.append(input())
    
    for r in range(H):
        for c in range(W):
            if field[r][c] == "
                row[r] += 1
                column[c] += 1
                total += 1

    count = 0
    for r in range(2 ** H):
        for c in range(2 ** W):
            dub = []
            delete = 0
            overdelete = 0
            for i in range(H):
                if r >> i & 1:
                    dub.append(field[i])
                    delete += row[i]
            for i in range(W):
                if c >> i & 1:
                    delete += column[i]
                    for d in dub:
                        if d[i] == "
                            overdelete += 1
            
            if total - delete + overdelete == K:
                
                count += 1

    print(count)

    return 

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product
H, W, K = map(int, input().split())
c = []
r = [0]* W
S = [input() for _ in range(H)]
for i in range(H):
    c.append(S[i].count('
for i in range(W):
    for j in range(H):
        if S[j][i] == '

nall = sum(c)
ans = 0
for hh in product([0, 1], repeat=H):
    for ww in product([0, 1], repeat=W):
        dl = 0
        for ih, ihh in enumerate(hh):
            dl += c[ih] * ihh
            for iw, iww in enumerate(ww):
                if S[ih][iw] == '
                    dl -= ihh * iww
        for iw, iww in enumerate(ww):
            dl += r[iw] * iww
        
        if nall - dl == K: ans += 1
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
c = [input() for _ in range(H)]

import copy
import itertools
c_copy = copy.deepcopy(c)

tate_options = list(itertools.product([0,1],repeat=W))
yoko_options = list(itertools.product([0,1],repeat=H))

answer = 0
for tate_option in tate_options:
    for yoko_option in yoko_options:
        count = 0
        for i in range(W):
            if tate_option[i] == 1:
                continue
            for j in range(H):
                if yoko_option[j]==1:
                    continue

                if c[j][i] == "
                    count += 1
        if count == K:
            answer += 1
print(answer)

Solution (Python):
h, w, k = map(int, input().split())
c = [[] for _ in range(h)]
numC, numR = [], []
for i in range(h):
    c[i] = list(input())

from itertools import permutations, product
from copy import deepcopy

res = 0

for u in product([0, 1], repeat=h): 
    for v in product([0, 1], repeat=w): 
        tmp = deepcopy(c)
        for i in range(h):
            if u[i] == 0:
                for j in range(w):
                    if tmp[i][j] == '
                        tmp[i] = '.' * w
        for i in range(w):
            if v[i] == 0:
                for j in range(h):
                    if tmp[j][i] == '
                        tmp[j][i] = '.'
        
        cnt = 0
        for j in range(h):
            for i in range(w):
                if tmp[j][i] == '
                    cnt += 1
        if cnt == k:
            res += 1

print(res)

Solution (Python):

import sys



input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


H, W, K = MI()
c = [list(S()) for _ in range(H)]



ans = 0
for h in range(1 << H):
    for w in range(1 << W):
        count = 0
        for j in range(H):
            for i in range(W):
                if not ((h >> j) & 1) and not ((w >> i) & 1) and c[j][i] == "
                    count += 1
        if count == K:
            ans += 1

print(ans)

Solution (Python):
import itertools
import copy

H, W, K = map(int, input().split()) 
Graph = []
for i in range(H):
    tmp = list(input())
    Graph.append(tmp)

ans = 0
for i in itertools.product(range(2), repeat=(H+W)):
    G = copy.deepcopy(Graph)
    for j in range(H+W):
        if 0 <= j < H:
            if i[j] == 1:
                G[j] = ["r"]*W
        else:
            if i[j] == 1:
                for h in range(H):
                    G[h][j-H-1] = "r"
                    
    cnt = 0
    for h in range(H):
        for w in range(W):
            if G[h][w] == "
                cnt += 1
                
    if cnt == K:
        ans += 1 

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

import itertools

h, w, k = map(int, input().split())
field = [input() for _ in range(h)]

field = [list(f) for f in field]

black_h = {}
black_w = {}
black_i = {}

tot = 0

for ih in range(h):
    for iw in range(w):
        black_h[ih] = 0
        black_w[iw] = 0
        black_i[(ih,iw)] = 0

for ih in range(h):
    for iw in range(w):
        if field[ih][iw] == '
            black_h[ih] += 1
            black_w[iw] += 1
            black_i[(ih,iw)] += 1
            tot += 1
            





ans = 0

for n_comb_h in range(h+1):
    for v_h in itertools.combinations([i for i in range(h)],n_comb_h):
        for n_comb_w in range(w+1):
            for v_w in itertools.combinations([i for i in range(w)],n_comb_w):
                tmp = 0
                for i_h in v_h:
                    tmp += black_h[i_h]
                for i_w in v_w:
                    tmp += black_w[i_w]
                for i_h in v_h:
                    for i_w in v_w:
                        if black_i[(i_h, i_w)] == 1:
                            tmp -= 1
                if tmp == tot-k:
                    ans += 1
                    
print(ans)

Solution (Python):
def change_and_check(arr,rowarr,colarr,k):
	
	for i in range(len(rowarr)):
		ele=rowarr[i]
		for j in range(len(arr[0])):
			arr[ele][j]="r" 
	for i in range(len(colarr)):
		ele=colarr[i]
		for j in range(len(arr)):
			arr[j][ele]="r" 
	
	return count(arr)==k  
def count(arr):
	c=0 
	for i in range(len(arr)):
		for j in range(len(arr[0])):
			if arr[i][j]=="
				c+=1 
	return c
import itertools 
from copy import copy, deepcopy
frow=[] 
fcol=[] 
h,w,k=map(int,input().split()) 
a=[] 
f=list(range(h))
g=list(range(w))
for i in range(h):
	n=input()
	a.append(list(n))
for kk in range(h+1):
	l=list(map(list,itertools.combinations(f,kk)))
	frow+=l
for kk in range(w+1):
	l=list(map(list,itertools.combinations(g,kk)))
	fcol+=l 

arr=deepcopy(a)

cc=0 

for x in frow:
	for y in fcol:
		
		if change_and_check(a,x,y,k):
			cc+=1 
		a=deepcopy(arr)
print(cc)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from itertools import product
import copy

H,W,K = LI()
c = [list(map(str,input())) for _ in range(H)]

def count(S):
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '
                ans += 1
    return ans

A = list(product([True,False],repeat=H))
B = list(product([True,False],repeat=W))

num = 0
for a in A:
    for b in B:
        S = copy.deepcopy(c)
        for i in range(H):
            if a[i]:
                for j in range(W):
                    S[i][j] = '?'
        for j in range(W):
            if b[j]:
                for i in range(H):
                    S[i][j] = '?'
        co = count(S)
        if co == K:
            num += 1

print(num)

Solution (Python):
h,w,k=map(int,input().split())
c=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]
ans=0
for i in range(h):
    a=input()
    for j in range(w):
        c[i][j]=a[j]
for i in range(2**(h+w)):
    for m in range(h):
        for n in range(w):
            d[m][n]=c[m][n]
    for j in range(h):
        if (i >> j)&1:
            for x in range(w):
                d[j][x]="r"
    for j in range(h,w+h):
        if (i >> j)&1:
            for x in range(h):
                d[x][j-h]="r"
    f=0
    for q in range(h):
        for s in range(w):
            if d[q][s]=="
                f+=1
            
        
    if f==k:
        ans+=1
print(ans)

Solution (Python):
h, w, k = map(int, input().split())
field = list(list(input()) for i in range(h))

def red():
    res = 0
    for i in range(h):
        for j in range(w):
            if field[i][j] == '
                res += 1
    return res

cnt = 0
for s in range(2 ** h):
    for t in range(2 ** w):

        for i in range(h):
            for j in range(w):
                if ((s >> i) & 1):
                    for x in range(w):
                        if field[i][x] == '
                            field[i][x] = 'r'
                if ((t >> j) & 1):
                    for x in range(h):
                        if field[x][j] == '
                            field[x][j] = 'r'
        if red() == k:
            cnt += 1
        for x in range(h):
            for y in range(w):
                if field[x][y] == 'r':
                    field[x][y] = '

print(cnt)

Solution (Python):
from copy import deepcopy
h, w, k = map(int, input().split())
C = [[c for c in input()] for _ in range(h)]


def black(G):
    tmp = 0
    for hh in range(h):
        for ww in range(w):
            if G[hh][ww] == "
                tmp += 1
    return tmp


def main():
    ans = 0
    for i in range(2**h):
        tmp = i
        T = deepcopy(C)
        for hh in range(h):
            if tmp % 2 == 1:
                tmp = tmp // 2
                continue
            tmp = tmp // 2
            for ww in range(w):
                T[hh][ww] = "r"
        for j in range(2**w):
            U = deepcopy(T)
            tmp2 = j
            for ww in range(w):
                if tmp2 % 2 == 1:
                    tmp2 = tmp2 // 2
                    continue
                tmp2 = tmp2 // 2
                for hh in range(h):
                    U[hh][ww] = "r"
            if black(U) == k:
                ans += 1
    print(ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):
import copy
H,W,K=map(int,input().split())
c=[]
ANS=0
for i in range(H):
    c.append(list(input()))
for i in range(2**H):
    for j in range(2**W):
        C=copy.copy(c)
        ans=0
        for k in range(H):
            if (i>>k)&1==1:
                C[k]=['.' for i in range(W)]
        for l in range(W):
            if (j>>l)&1==1:
                C=list(zip(*C))
                C[l]=['.' for i in range(H)]
                C=list(zip(*C))
        for s in C:
            for a in s:
                if a=='
                    ans+=1
        if ans==K:
            ANS+=1
print(ANS)

Solution (Python):
import copy

H,W,K=list(map(int,input().split()))

C=list()
Cd=list()
for h in range(H):
    S = input()
    C.append(S)

    r=list()
    for w in range(W):
        if S[w] == '.':
            d=0
        else:
            d=1
        r.append(d)
    Cd.append(list(r))

ans=0

def check_bits(i,width):
    c = list()
    for w in range(width):
        c.append(1 & (i>>w))
    return c

ans=0
for h in range(2**H):
    check = copy.deepcopy(Cd)

    hsel = check_bits(h,H)
    

    for i in range(H):
        if hsel[i]==1:
            check[i]=[0] * W

    
    for w in range(2**W):
        check_w = copy.deepcopy(check)

        wsel = check_bits(w,W)
        

        for j in range(W):
            if wsel[j] == 1:
                for i in range(H):
                    check_w[i][j] = 0
        
        calc = 0
        for i in range(H):
            calc += sum(check_w[i])
        
        if calc == K:
            ans += 1
print(ans)

Solution (Python):
H, W, K = map(int, input().split())

hw = []
for i in range(H):
    w = list(input())
    hw.append(w)


def check(h_ok, w_ok):
    sum = 0
    for h in range(H):
        for w in range(W):
            if h_ok[h] == 0 and w_ok[w] == 0 and hw[h][w] == "
                sum+=1
    return sum == K


result = 0

for h1 in [0, 1]:
    for h2 in [0, 1]:
        for h3 in [0, 1]:
            for h4 in [0, 1]:
                for h5 in [0, 1]:
                    for h6 in [0, 1]:
                        for w1 in [0, 1]:
                            for w2 in [0, 1]:
                                for w3 in [0, 1]:
                                    for w4 in [0, 1]:
                                        for w5 in [0, 1]:
                                            for w6 in [0, 1]:
                                                h_ok = {}
                                                w_ok = {}
                                                h_ok[0] = h1
                                                h_ok[1] = h2
                                                h_ok[2] = h3
                                                h_ok[3] = h4
                                                h_ok[4] = h5
                                                h_ok[5] = h6
                                                w_ok[0] = w1
                                                w_ok[1] = w2
                                                w_ok[2] = w3
                                                w_ok[3] = w4
                                                w_ok[4] = w5
                                                w_ok[5] = w6
                                                if check(h_ok, w_ok):
                                                    result+=1
for h in range(6-H+6-W):
    result /= 2

print(int(result))

Solution (Python):
h, w, k = map(int, input().split())
c = [list(input()) for i in range(h)]

h1 = [list(f"{i:0{h}b}") for i in range(2**h)]
w1 = [list(f"{i:0{w}b}") for i in range(2**w)]

cnt = 0
for hh in h1:
    for ww in w1:
        black = 0
        x = [i for i in range(h) if hh[i]=='1']
        y = [i for i in range(w) if ww[i]=='1']
        for i in x:
            for j in y:
                if c[i][j] == '
                    black += 1
        if black == k:
            cnt += 1
            

print(cnt)

Solution (Python):
from itertools import combinations
from copy import deepcopy
H, W, K = map(int, input().split())
field = [[c for c in input()] for i in range(H)]

def hmblack(field):
    count = 0
    for l in field:
        for c in l:
            if c == '
                count += 1
    return count

result = 0

for i in range(H+1):
    dline = combinations(range(H), i)
    for cl in dline:
        for j in range(W+1):
            draw = combinations(range(W), j)
            for cr in draw:
                cpf = deepcopy(field)
                for y in range(H):
                    for x in range(W):
                        if y in cl or x in cr:
                            cpf[y][x] = 'r'
                if hmblack(cpf) == K:
                    result += 1
print(result)

Solution (Python):

import sys

from sys import stdin
input = lambda: stdin.readline().rstrip()


H, W, K = map(int,input().split())

c = []

for i in range(H):
    c.append(list(input()))

answer = 0
def count(h_target, w_target):
    cnt = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == '
                cnt+=1
    if cnt == K:
        return 1
    else:
        return 0

h_format = '0' + str(H) + 'b'
w_format = '0' + str(W) + 'b'
for h in range(2**(H)):
    for w in range(2**(W)):
        
        
        
        h_target = [n for n, v in enumerate(list(format(h,h_format))) if v == '1']
        w_target = [n for n, v in enumerate(list(format(w,w_format))) if v == '1']
        
        
        
        answer += count(h_target,w_target)

print(answer)