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):
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import Counter
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, W, K = map(int, readline().split())
    C = read().split()
    black = 0
    low = [0]*H
    column = [0]*W
    for h in range(H):
        c = C[h]
        b = c.count('
        black += b
        low[h] = b
        for w in range(W):
            if c[w]=='
                column[w]+=1
    ans = 0
    for i in range(2**H):
        for j in range(2**W):
            loss = 0
            for h in range(H):
                if ((i>>h)&1)==1:
                    loss += low[h]
                    for w in range(W):
                        if ((j>>w)&1) == 1:
                            if C[h][w]=='
                                loss -= 1
            for w in range(W):
                if ((j >> w)&1) == 1:
                    loss += column[w]
            if black-loss == K:
                ans += 1
    print(ans)



if __name__ == '__main__':
    main()

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

def li():
    return [int(x) for x in input().split()]

H, W, K = li()
c = [list(input()) for x in range(H)]

def checkCount(m):
    cnt = 0
    for l in m:
        cnt += l.count('
    return cnt

result = 0
for h in range(H+1):
    comh = list(combinations(range(H),h))
    sm = 0
    for x in comh:
        cr = [c[i] if i not in x else [0]*W for i in range(H)]
        crt = np.array(cr).T.tolist()
        for w in range(W+1):
            comw = list(combinations(range(W),w))
            for y in comw:
                z = [crt[j] for j in range(W) if j not in y]
                if checkCount(z) == K:
                    result += 1

print(result)

Solution (Python):
from itertools import combinations
from copy import deepcopy
h,w,d = map(int,input().split())
c = []
kuro = 0
for i in range(h):
    s = list(input())
    kuro += s.count("
    c.append(s)
ans = 0
for i in range(h):
    for j in range(w):
        for k in combinations(range(h),r=i):
            for l in combinations(range(w),r=j):
                data = deepcopy(c)
                num = 0
                for m in k:
                    for a in range(w):
                        if data[m][a] == "
                            data[m][a] = "."
                            num += 1
                for n in l:
                    for b in range(h):
                        if data[b][n] == "
                            num += 1
                if kuro-num == d:
                    ans += 1
print(ans)

Solution (Python):
import copy
row,col,kkk = map(int,input().split())
matrix = []
for i in range(row):
  matrix.append(list(input()))
combination = set()
rowcol=[]
for i in range(row):
  rowcol.append((i,0))
for i in range(col):
  rowcol.append((i,1))
  
def find(index,temp):
    if index==len(rowcol):
      combination.add(tuple(copy.deepcopy(temp)))
      return 
    find(index+1,temp+[rowcol[index]])
    find(index+1,temp)
find(0,[])
new = set()
combination = list(combination)
for i in combination:
  i = list(i)
  i.sort()
  i = tuple(i)
  new.add(i)
ans = 0
for i in new:
  
  tempmatrix = copy.deepcopy(matrix)
  for j in i:
    
    temp,flag = j
    if flag == 0:
        for k in range(col):
          tempmatrix[temp][k] = 0
    if flag == 1:    
        for l in range(row):
            tempmatrix[l][temp] = 0
  
  black = 0
  for m in range(row):
    for n in range(col):
      if tempmatrix[m][n] == "
        black += 1
  if black == kkk:
    ans += 1
print(ans)

Solution (Python):
a = list(map(int,input().split()))
b = [input() for l in range(a[0])]
ans = 0
cnt = 0
allcnt = 0
nongyou = []
cnt2 = 0
for i in range(a[0]):
    allcnt += b[i].count('

for i in range(2 ** a[0]):
    cnt = allcnt
    nongyou = []
    for j in range(a[0]):
        if ((i >> j) & 1):
            cnt -= b[j].count('
            nongyou.append(j)
    for m in range(2 ** a[1]):
        cnt2 = cnt
        for n in range(a[1]):
            if ((m >> n) & 1):
                for k in range(a[0]):
                    if k in nongyou:
                        continue
                    else:
                        cnt2 -= b[k][n].count('
        if cnt2 == a[2]:
            ans += 1

print(str(ans))

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

height, width, black = map(int, sys.stdin.readline().split())
mat = np.array([list(input()) for _ in range(height)])
n_black_remove = np.sum(mat == "
n_black_row = np.array([np.sum(mat[row, :] == "
n_black_col = np.array([np.sum(mat[:, col] == "
result = 0

for n_delete_row in range(height+1):
    for n_delete_col in range(width+1):
        for combi_row in combinations(range(height), n_delete_row):
            for combi_col in combinations(range(width), n_delete_col):
                remove = 0
                if combi_row:
                    remove += np.sum(n_black_row[list(combi_row)])
                if combi_col:
                    remove += np.sum(n_black_col[list(combi_col)])
                for r, c in product(combi_row, combi_col):
                    if mat[r][c] == "
                        remove -= 1
                if remove == n_black_remove:
                    result += 1
print(result)

Solution (Python):
import itertools
import copy
h,w,k=map(int,input().split())
c = [list(input()) for _ in range(h)]
x = itertools.product(range(2) , repeat=h+w)
ans = [0] * (h+w)

tmp = []
for q in x:
  tmp = copy.deepcopy(c)
  for i in range(h):
    if q[i] == 1:
      tmp[i] = ["r"] * w
    else :
      tmp[i] = copy.deepcopy(c[i])

  for j in range(w):
    if q[h+j] == 1:
      for i in range(h):
        tmp[i][j] = "r"
  tans = 0
  for i in range(h):
    for j in range(w):
      tans += tmp[i][j].count("
  ans.append(tans)
cnt = 0

for a in ans:
  if a == k :
    cnt += 1
  
print(cnt)

Solution (Python):
def countRowColumn(color):
    blackr = []
    for i in range(row):
        blackr.append(color[i].count('
    blackc = []
    for i in range(col):
        c = 0
        for j in range(row):
            if color[j][i]=='
                c+=1
        blackc.append(c)
    
def counting(color):
    t=0
    for c in color:
        t+=c.count('
    return t
def func(color,setr,setc,r,c):
    counts = counting(color)
    if counts<k:
        return 0
    if counts==k:
        dp.add((tuple(sorted(setr)),tuple(sorted(setc))))
    
    
    for i in range(r,row):
        temp = []
        for j in range(col):
            temp+=[color[i][j]]
            color[i][j]='R'
        setr.add(i)
        func(color,setr,setc,i+1,c)
        setr.remove(i)
        for j in range(col):
            color[i][j]=temp[j]
    for j in range(c,col):
        temp = []
        for i in range(row):
            temp+=[color[i][j]]
            color[i][j]='R'
        setc.add(j)
        func(color,setr,setc,r,j+1)
        setc.remove(j)
        for i in range(row):
            color[i][j]=temp[i]
    return 0
    
dp = set()
row, col, k = map(int,input().split())
color = []
blackr = []
for _ in range(row):
    color.append(list(input()))
    blackr.append(color[-1].count('
blackc = []
for i in range(col):
    c = 0
    for j in range(row):
        
        if color[j][i]=='
            c+=1
    blackc.append(c)
total = sum(blackr)

if total<k:
    print(0)
else:
    func(color,set(),set(),0,0)
    print(len(dp))

Solution (Python):
import itertools

h, w, k = tuple(map(int, input().split()))
k2 = k
c = ''
for _ in range(h):
    c += input()

grid = []
for i in c:
    if i == '
        grid.append(1)
    else:
        grid.append(2)

ans = 0
for i in range(h+1):
    for j in list(itertools.combinations(range(h), i)):
        for k in range(w+1):
            for l in list(itertools.combinations(range(w), k)):
                tmp = grid[:]
                for j2 in j:
                    tmp[w*j2:w*(j2+1)] = [3] * w
                for l2 in l:
                    tmp[l2::w] = [3] * h
                if tmp.count(1) == k2:
                    ans += 1

print(ans)

Solution (Python):

import collections
import sys
import copy
import re


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    H, W, K = LI()
    c = []

    N = H+W
    for i in range(H):
        c.append(list(S()))

    ans = 0
    for i in range(2**N):
        cow = []
        row = []
        cCopy = copy.deepcopy(c)
        blacks = 0
        for j in range(N):
            if ((i >> j) & 1):  
                if j >= W:
                    row.append(j)
                else:
                    cow.append(j)
        for h in range(H):
            if (h+W) in row:
                continue
            else:
                for w in range(W):
                    if w in cow:
                        continue
                    if cCopy[h][w] == "
                        blacks += 1

        if blacks == K:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import itertools
H, W, K = map(int, input().split())
ans = 0
c = []
for _ in range(H):
  c.append(list(input()))
c = np.array(c)

for l in list(itertools.product([True,False], repeat=H)):
  for l2 in list(itertools.product([True,False], repeat=W)):
    c2 = c.copy()
    c2[l, :] = 'R'
    c2[:, l2] = 'R'
    if (c2== '
      ans += 1

print(ans)

Solution (Python):
H,W,K = map(int, input().split())
a =[list(input()) for i in range(H)]
import copy


l=0

for i in range(2**W):
    q=str(format(i, '0{}b'.format(W)))
    
    
    b=copy.deepcopy(a)
    
    for u in range(W):
        if q[u]=='1':
            for y in range(H):
                b[y][u]='&'
                
    for i in range(2**H):
        c=copy.deepcopy(b)
        num=0
        e=str(format(i, '0{}b'.format(H)))
        for t in range(H):
            if e[t]=='1':
                for y in range(W):
                    c[t][y]='.'
        
        num=0
        for h in range(H):
                for w in range(W):
                    if c[h][w]=='
                        num+=1
        if num==K:
            l+=1
print(l)

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

cc = []
for i in range(h):
    cc.append([])
    for j in range(w):
        cc[i].append(c[i][j])

ccc = []
for i in range(h):
    ccc.append([])
    for j in range(w):
        ccc[i].append(c[i][j])

import copy




cnt2 = 0
for i in range(2**h):
    for j in range(2**w):
        
        cc = copy.deepcopy(ccc)
        ii = bin(i)[2:].zfill(h)
        jj = bin(j)[2:].zfill(w)
        
        
        for k in range(len(ii)):
            if ii[k] == '1':
                for l in range(w):
                    cc[k][l] = '0'
        for k in range(len(jj)):
            if jj[k] == '1':
                for l in range(h):
                    cc[l][k] = '0'
        cnt = 0
        for k in range(h):
            for l in range(w):
                if cc[k][l] == '
                    cnt += 1
        if cnt == kk:
            cnt2 += 1
            
        
print(cnt2)

Solution (Python):

H,W,K=map(int,input().split())
C=[]
for i in range(H):
  tmp=input()
  C+=[tmp]
ans=0
Hlis=[0 for i in range(H)]
Wlis=[0 for j in range(W)]
def Hsin(n):
  t=H-1
  while t>0:
    tmpo=n//(2**t)
    Hlis[H-1-t]=tmpo
    n=n%(2**t)
    t-=1
  Hlis[-1]=n
  return Hlis
def Wsin(n):
  t=W-1
  while t>0:
    tmpo=n//(2**t)
    Wlis[W-1-t]=tmpo
    n=n%(2**t)
    t-=1
  Wlis[-1]=n
  return Wlis

res=0
for l in range(H):
  for m in range(W):
    if C[l][m]=="
      res+=1
K2= res-K


ans=0


for i in range(2**H):
  r=Hsin(i)
  for j in range(2**W):
    co=Wsin(j)
    res=0
    for l in range(H):
      for m in range(W):
        if (r[l]==1) or (co[m]==1 ):
          if C[l][m]=="
            res+=1
    if res==K2:
      ans+=1
print(ans)

Solution (Python):

h, w, k = map(int, input().split())

c = [list(input()) for l in range(h)]

cnt = 0

for i in range(w):
    for j in range(h):
        if c[j][i] == "
            cnt += 1

ans = 0
ans2 = 0
s = []
for i in range(w):
    s.append(i)

t = []
for i in range(h):
    t.append(i)


n = len(s)
for i in range(2 ** n):
    bag = []
    for j in range(n):
        if (i >> j) & 1:
            bag.append(s[j])
    n2 = len(t)
    for i11 in range(2 ** n2):
        bag2 = []
        for j in range(n2):
            if (i11 >> j) & 1:
                bag2.append(t[j])
        
        
        d = 0
        for i3 in bag:
            for i2 in range(h):
                if c[i2][i3] == "
                    d += 1
            for j3 in bag2:
                if c[j3][i3] == "
                    d -= 1

        for j3 in bag2:
            for j2 in range(w):
                if c[j3][j2] == "
                    d += 1

        if cnt - d == k:
            ans += 1

print(ans)

Solution (Python):
import itertools

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

yoko = [i for i in range(w)]
tate = [i for i in range(h)]
ans = 0

for i in range(w+1):
    for u in itertools.combinations(yoko, i):
        

        for j in range(h+1):
            for v in itertools.combinations(tate, j):
                
                

                
                poi = 0
                
                for ii in range(w):
                    if not ii in u:
                        
                        for jj in range(h):
                            if not jj in v:
                                
                                if c[jj][ii]=='
                                    poi += 1
                if poi == k:
                    ans += 1
                
print(ans)

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

matrix=[]
for i in range(H):
    matrix.append(input())

ans=0

comb_b=[j for j in range(2**W)]

comb=[(i,comb_b) for i in range(2**H)]

for i in range(2**H):
    for j in range(2**W):
        count=0
        for k in range(H):
            for l in range(W):
                if ((0b1<<k) & comb[i][0]) or ((0b1<<l) & comb[i][1][j]):
                    pass
                else:
                    if matrix[k][l]=="
                        count+=1
        if count==K:
            ans+=1

print(ans)

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

count = 0
he = [0 for i in range(h)]
for i in range(2**h):
    we = [0 for i in range(w)]

    h_set = set(range(h))
    for j in range(h):
        if(he[j] == 0):
            h_set.discard(j)
    h_a = list(h_set)
    for j in range(h):
        if(he[h-j-1] == 0):
            he[h-j-1] = 1
            for k in range(h-j,h):
                he[k] = 0
            break

    for j in range(2**w):
        w_set = set(range(w))
        for k in range(w):
            if(we[k] == 0):
                w_set.discard(k)
        w_a = list(w_set)
        for k in range(w):
            if(we[w-k-1] == 0):
                we[w-k-1] = 1
                for m in range(w-k,w):
                    we[m] = 0
                break


        black = 0
        for x in h_a:
            for y in w_a:
                if(c[x][y] == '
                    black += 1
        if(black == K):
            count += 1
 
        

print(count)

Solution (Python):
import copy

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

ans = 0
for i in range(2 ** H):
    row_colored_board = copy.deepcopy(board)
    for ii in range(H):
        if (i >> ii) & 1:
            row_colored_board[ii] = list('*' * W)
    for j in range(2 ** W):
        cnt = 0
        col_colored_board = copy.deepcopy(row_colored_board)
        for jj in range(W):
            if (j >> jj) & 1:
                for k in range(H):
                    col_colored_board[k][jj] = '*'
        for l in range(H):
            for m in range(W):
                if col_colored_board[l][m] == '
                    cnt += 1
    
        if cnt == K:
            ans += 1

print(ans)

Solution (Python):
def grinp(h):
  ret=[]
  for i in range(h):
    ret.append(list(input()))
  return ret
h,w,k=map(int,input().split())
gr=grinp(h)
ans=0
for i in range(2**h):
  chx=[]
  for j in range(h):
    if((i>>j)&1):
      chx.append(j)
  for j in range(2**w):
    chy=[]
    for kk in range(w):
      if ((j>>kk)&1):
        chy.append(kk)
    com=0
    for kk in range(h):
      for l in range(w):
        if kk in chx or l in chy:
          continue
        if gr[kk][l]=="
          com+=1
    if com==k:
      ans+=1
print(ans)

Solution (Python):
h, w, kk = map(int, input().split())

c = []
for i in range(h):
  c.append(input())

cnt = 0
for i in range(2**(h+w)):
  total = 0
  for j in range(h):
    if ((i >> j) & 1):
      for k in range(w):
        if ((i >> (h+k)) & 1) and c[j][k] == '
          total += 1
  if total == kk:
    cnt += 1

print(cnt)

Solution (Python):
def dfs(i, m, l):
    if i == m:
        return [l]
    ans = dfs(i+1, m, l+[i])
    ans += dfs(i+1, m, l)
    return ans


def main():
    H, W, K = map(int, input().split())
    M = [input() for _ in range(H)]
    r_cnt = [0]*H
    c_cnt = [0]*W
    for i, row in enumerate(M):
        for j, c in enumerate(row):
            if row[j] == "
                r_cnt[i] += 1
                c_cnt[j] += 1
    ans = 0
    bc = 0
    r_combi = dfs(0, H, [])
    c_combi = dfs(0, W, [])
    for rc in r_combi:
        for cc in c_combi:
            for r in rc:
                bc += r_cnt[r]
            for r in rc:
                for c in cc:
                    if M[r][c] == "
                        bc -= 1
            if bc == K:
                ans += 1
            bc = 0
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
h,w,k = map(int, input().split())
l = []
lh = []
lw = []
s = 0
r = 0
for i in range(h):
    il = input()
    l.append(il)
    s += il.count('
    lh.append(il.count('
for i in range(w):
  j = 0
  for il in l:
    if il[i] == '
      j += 1
  lw.append(j)
    
t = s - k
if t == 0:
    r += 1
    
from itertools import combinations

for nh in range(1,h+1):
  for ih in combinations(range(h), nh):
    if sum([lh[x] for x in ih]) == t:
      r += 1
      
for nw in range(1,w+1):
  for iw in combinations(range(w), nw):
    if sum([lw[x] for x in iw]) == t:
      r += 1
      
for nh in range(1,h+1):
    for nw in range(1,w+1):
        for ih in combinations(range(h), nh):
            for iw in combinations(range(w),nw):
                ik = sum([lh[x] for x in ih]) + sum([lw[x] for x in iw])
                for jh in ih:
                    for jw in iw:
                        if l[jh][jw] == '
                            ik -= 1
                if ik == t:
                    r += 1
                    
print(r)

Solution (Python):
h, w, k = map(int, input().split())
import numpy as np
aa = np.zeros((h, w),dtype='int32')
for i in range(h):
    aa[i] = np.array([int(c=='
cnt = 0
for i in range(2**w):
    col = np.array([int(i&(2**j)>0) for j in range(w)])
    tmp = aa.dot(col)
    for p in range(2**h):
        row = np.array([int(p&(2**l)>0) for l in range(h)])
        if np.sum(tmp*row) == k:
            cnt += 1
print(cnt)

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

import numpy as np

A = np.zeros([H,W])
cntResult = 0

for i in range(H):
    B = input()
    for j in range(W):
        if B[j] == '.':
            A[i,j] = 0
        else:
            A[i,j] = 1

sumA = np.sum(A)
sumH = [0]*H
sumW = [0]*W
for i in range(H):
    sumH[i] = np.sum(A[i,:])

for i in range(W):
    sumW[i] = np.sum(A[:,i])


for i in range(2**H):
    cntH = format(i, '0%db' % H)
    for j in range(2**W):
        cntW = format(j, '0%db' % W)
        result = 0
        for k in range(H):
            for l in range(W):
                if int(cntH[k]) == 0 and int(cntW[l]) == 0:
                    result += A[k,l]
        if result == K:
            cntResult += 1

print(cntResult)

Solution (Python):
import numpy as np
import copy
from itertools import combinations
H,W,K=list(map(int,input().split()))
C1=[list(input()) for i in range(H)]
C1=np.array(C1)
listH=[i for i in range(H)]
listW=[i for i in range(W)]
listH2=[]
listW2=[]
for i in range(0,H+1):
    listH2.append(list(combinations(listH,i)))
listH2=[flat for i in listH2 for flat in i]

for i in range(0,W+1):
    listW2.append(list(combinations(listW,i)))
listW2=[flat for i in listW2 for flat in i]

ans=0
for h in listH2:
    for w in listW2:
        ans2=0
        C=copy.deepcopy(C1)
        if h!=():
            for i in h:
                C[i]='.'
        if w!=():
            for j in w:
                C[:,j]='.'
        for i in C:
            for j in i:
                if j=='
                    ans2+=1
        if ans2==K:
            ans+=1
print(ans)

Solution (Python):
import numpy as np
import itertools
H , W , K = map(int,input().split())
C = [['' for i in range(W)] for j in range(H)]
c = [[0 for i in range(W)] for j in range(H)]
c = np.array(c) 
for i in range(H):
  C[i] = list(str(input()))
  
C = np.array(C)  
for i in range(W):
  for j in range(H):
    if C[j,i] == '
      c[j,i] = 1
Y = [i for i in range(H)]
X = [i for i in range(W)]
S = 0
for n in range(0,len(X) + 1):
  for comb in itertools.combinations(X,n):
    cdum = np.array(c)
    for i in comb:
      for k in range(H):
        cdum[k,i] = 0
    cdumx = np.array(cdum)
    for m in range(0,len(Y) + 1):
      for Comb in itertools.combinations(Y,m):
        for j in Comb:
          for k in range(W):
            cdumx[j,k] = 0
        if np.sum(cdumx) == K:
          S += 1
        cdumx = np.array(cdum)
print(S)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    h, w, k = LI()
    c = SR(h)
    ans = 0
    for mask in range(1 << h):
        for mask2 in range(1 << w):
            tmp = 0
            for hi in range(h):
                for wi in range(w):
                    if mask & 1 << hi or mask2 & 1 << wi: continue
                    if c[hi][wi] == "
                        tmp += 1
            if tmp == k: ans += 1
            
    print(ans)


    return



if __name__ == '__main__':
    solve()

Solution (Python):
import copy

H, W, K = map(int, input().split())
C = [list(input()) for i in range(H)]
ans = 0

for n in range(1 << (H + W)):
    c = copy.deepcopy(C)
    for i in range(H):  
        if (n >> i) & 1 == 1:
            for w in range(W):  
                c[i][w] = "r"
    for j in range(H, H + W):
        if (n >> j) & 1 == 1:
            for h in range(H):
                c[h][j - H] = "r"

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

print(ans)

Solution (Python):
import sys
import itertools

import numpy as np

first, second, k = tuple(map(int, sys.stdin.readline().split()))

array = np.full(shape=(first, second), fill_value=0, dtype=np.int32)

for i, line in enumerate(sys.stdin):
  for j, c in enumerate(line.strip()):
    array[i, j] = 1 if c == '







count = 0
def index_iter(size):
  indexes = list(range(size))
  for L in range(1, len(indexes)+1):
      for subset in itertools.combinations(indexes, L):
        yield list(subset)

for v_index in index_iter(first):
  for h_index in index_iter(second):
    
    
    

    if np.sum(array[v_index][:, h_index]) == k:
      count += 1

print(count)

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



def calc_black(field):
  co = 0
  for i in field:
    for j in i:
      if j == "
        co += 1
  return co

import copy
import itertools

aaa = list(itertools.product([0,1],repeat = H ))
bbb = list(itertools.product([0,1],repeat = W ))


count = 0
for i in aaa:
  for j in bbb:
    c_tmp = copy.deepcopy(c)    
    for ind,ii in enumerate(i):
      if(ii):
        c_tmp[ind] = ["r"]*W
    for ind,jj in enumerate(j):
      if (jj):
        for iii in range(H):
          c_tmp[iii][ind] = "r"
          
    if K == calc_black(c_tmp):
      count += 1


print(count)

Solution (Python):
import pprint

def main():
    h, w, k = list(map(int, input().split()))
    
    black_num_in_each_row = [0 for _ in range(h)]
    black_num_in_each_column = [0 for _ in range(w)]
    black_num = 0
    black_coords = []

    match_condition_count = 0

    for hi in range(h):
        chars = input()
        black_num_in_each_row[hi] = chars.count("
        for wi, c in enumerate(chars):
            if c == "
                black_num_in_each_column[wi] += 1
                black_coords.append((hi, wi))
                black_num += 1

    
    
    
    

    for hi in range(2 ** h):
        for wi in range(2 ** w):
            h_bin = '{0:0b}'.format(hi).zfill(h)
            w_bin = '{0:0b}'.format(wi).zfill(w)
            current_pattern_black_num = black_num

            
            for ri, r in enumerate(h_bin):
                if r == "1":
                    current_pattern_black_num -= black_num_in_each_row[ri]
            for ci, c in enumerate(w_bin):
                if c == "1":
                    current_pattern_black_num -= black_num_in_each_column[ci]
            
            for r, c in black_coords:
                if h_bin[r] == "1" and w_bin[c] == "1":
                    current_pattern_black_num += 1

            
            
            if current_pattern_black_num == k:
                match_condition_count += 1

    print(match_condition_count)


if __name__ == "__main__":
    main()

Solution (Python):
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import itertools as it

H, W, K = input_int()

maps = []



for h in range(H):
    maps.append(list(one_str()))

maps


cols_dict={i:[] for i in range(W+1)}


rows_dict={i:[] for i in range(H+1)}

sums = 0

for x in range(W):
    for y in range(H):
        if maps[y][x]=="
            cols_dict[x].append((y,x))
            rows_dict[y].append((y,x))
            sums+=1

count = 0
for x in range(W+1):
    xx = list(it.combinations([i for i in range(W)], x))
    
    for y in range(H+1):
        yy = list(it.combinations([i for i in range(H)], y))

        for xxx in xx:
            sum_set_x = set([])

            for xxxx in xxx:
                sum_set_x = sum_set_x | set(cols_dict[xxxx])
        
            for yyy in yy:
                sum_set_y = set([])
                for yyyy in yyy:
                    sum_set_y = sum_set_y | set(rows_dict[yyyy])

                sum_set = sum_set_x | sum_set_y
                if sums-len(sum_set) == K:
                    count+=1

print(count)

Solution (Python):
import itertools
h,w,k=map(int,input().split())
c=[list(input()) for _ in range(h)]
h_list=list(range(h))
w_list=list(range(w))
ans=0
cnt=0
for i in range(h):
  for j in range(w):
    if c[i][j]=="
      cnt+=1
if cnt==k:
  ans+=1
  
for i in range(1,h):
  for j in itertools.combinations(h_list, i):
    cnt=0
    for b in j: 
      cnt+=c[b].count("
    if cnt==k:
      ans+=1
      
for i in range(1,w):
  for j in itertools.combinations(w_list, i):
    cnt=0
    for b in j:
      for m in range(h):
        if c[m][b]=="
          cnt+=1
    if cnt==k:
      ans+=1

for i in range(1,h):
  for j in range(1,w):
    for l in itertools.combinations(h_list, i):
      for m in itertools.combinations(w_list, j):
        cnt=0
        for a in l:
          for b in m:
            if c[a][b]=="
              cnt+=1
        if cnt==k:
          ans+=1
print(ans)

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

count = 0

res = 0

c = []
for j in range(H):
    s = list(map(str, input()))
    c.append(s)
    count += s.count("

m = 0
for i in range(2 ** H):
    t = copy.deepcopy(c)
    count_tmp = copy.deepcopy(count)
    for j in range(H):
        if((i>>j) & 1):
            for a in range(W):
                if t[j][a] == "
                    t[j][a] = "@"
                    count_tmp -= 1
    for k in range(2 ** W):
        count_tmp2 = copy.deepcopy(count_tmp)
        t2 = copy.deepcopy(t)
        for l in range(W):
            if((k>>l) & 1):
                for b in range(H):
                    if t2[b][l] == "
                        t2[b][l] = "@"
                        count_tmp2 -= 1
        m += 1
        if count_tmp2 == K:
            res += 1

print(res)