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):
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    H, W, K = map(int, input().split())
    C = [input() for _ in [0] * H]

    ans, total = 0, 0
    for c in C:
        total += c.count('

    for mask in range(1 << H):
        c = C[:]
        x = []
        for i in range(H):
            if mask & 1 << i:
                x.append(i)
        n = total
        for i in x:
            n -= c[i].count('
            c[i] = '.' * W

        for mask in range(1 << W):
            k, y = n, []
            for i in range(W):
                if mask & 1 << i:
                    y.append(i)
            for i in range(H):
                for j in y:
                    if c[i][j] == '
                        k -= 1
            if k == K:
                ans += 1
    print(ans)


main()

Solution (Python):
h,w,k = map(int,input().split())
import copy
p = []
for i in range(h):
    q = input()
    q = list(q)
    p.append(q)
def kaz(p):
    an = 0
    for i in range(len(p)):
        for j in range(len(p[i])):
            if p[i][j] == '
                an += 1
    return an
ans = 0
for i in range(2**(h+w)):
    s = copy.deepcopy(p)
    u = copy.deepcopy(i)
    for j in range(h):
        if u & 1:
            s[j] = [0]*w
        u = u >> 1
    u = copy.deepcopy(i)
    u = u >> h
    for e in range(w):
        if u &1:
            for m in range(h):
                s[m][e] = 0
        u = u >> 1
    if kaz(s) == k:
        ans += 1
print(ans)

Solution (Python):


from pprint import pprint
import copy
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


H, W, K = map(int, input().split())
field = []
for _ in range(H):
    line = list(input())
    field.append(line)



def calc(field_copy):
    res = 0
    for i in range(H):
        for j in range(W):
            if field_copy[i][j] == '
                res += 1
    return res


res = 0
for row in range(2 ** H):
    for col in range(2 ** W):
        field_copy = copy.deepcopy(field)
        for i_row in range(H):
            if row & (1 << i_row):
                for j_col in range(W):
                    field_copy[i_row][j_col] = '_'
        for i_col in range(W):
            if col & (1 << i_col):
                for j_row in range(H):
                    field_copy[j_row][i_col] = '_'
        if calc(field_copy) == K:
            res += 1

print(res)

Solution (Python):
import copy
import itertools

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

for i in range(H):
    c = list(input())
    for j in range(W):
        squares[(i, j)] = c[j]

cs = []
for i in range(H + W + 1):
    cs += list(itertools.combinations(range(1, H + W + 1), i))

count = 0
for c in cs:
    copy_squares = copy.copy(squares)
    for x in c:
        if x <= H:
            for j in range(W):
                copy_squares[(x - 1, j)] = "."
        else:
            x -= H
            for i in range(H):
                copy_squares[(i, x - 1)] = "."
    if list(copy_squares.values()).count("
        count += 1
print(count)

Solution (Python):
import copy
h,w,kl = map(int, input().split(" "))
b=list(list(input()) for i in range(h))
count = 0
ans = 0
for i in range(h):
  for j in range(w):
    if b[i][j] == "
      count += 1
      
for hi in range(2 ** (h + w)):
  a = copy.deepcopy(b)
  temp = count
  for hj in range(h):
    if (hi >> hj) & 1:
      for l in range(w):
        if a[hj][l] == "
          temp -= 1
        a[hj][l] = "*"
  for wj in range(w):
    if (hi >> wj) & (2 ** h):
      for k in range(h):
        if a[k][wj] == "
          temp -= 1
        a[k][wj] = "*"
  if temp == kl:
    ans += 1 
  
  
print(ans)

Solution (Python):
import sys
import numpy as np


readline = sys.stdin.readline
read = sys.stdin.read

h, w, k = map(int, input().split())
a = np.array(list(read())).reshape([h,-1])[:,:-1]
b = np.where(a=='.', 0, 1)

ans = 0
for i in range(2**h):
    for j in range(2**w):
        I = np.array(list(format(i, '0'+str(h)+'b')), dtype=np.int64)
        J = np.array(list(format(j, '0'+str(w)+'b')), dtype=np.int64)
        if np.sum((b[I==1])[:,J==1]) == k:
            ans += 1
print(ans)

Solution (Python):
def main1():
    H,W,K=map(int,input().split())
    c=[input() for _ in range(H)]
    ans=0
    cn=0
    for i in range(2**H):
        t=str(bin(i))[2:]
        if len(t)!=H:
            t="0"*(H-len(t))+t
        for j in range(2**W):
            cn=0
            tt=str(bin(j))[2:]
            if len(tt)!=W:
                tt="0"*(W-len(tt))+tt
            
            for i_i,v_i in enumerate(t):
                for i_j,v_j in enumerate(tt):
                    if v_i =="0" and v_j == "0":
                        if c[i_i][i_j]=="
                                cn+=1
            if cn==K:
                ans+=1
    print(ans)
main1()

Solution (Python):
from copy import deepcopy
import itertools

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

maps = [list(input()) for _ in range(h)]
ans = 0

for i in range(2 ** h):
    for j in range(2 ** w):
        tmp_maps = deepcopy(maps)
        for x in range(h):
            if (i >> x) & 1:
                tmp_maps[x] = list('.' * w)
        for y in range(w):
            if (j >> y) & 1:
                for l in range(h):
                    tmp_maps[l][y] = '.'
        
        
        
        
        
        cnt = list(itertools.chain.from_iterable(tmp_maps)).count('
        if cnt == k:
            ans += 1

print(ans)

Solution (Python):
import copy

H, W, K = map(int, input().split())
C = [[c for c in input()] for _ in range(H)]
count = 0

for i in range(2 ** (H + W)):
    V = copy.deepcopy(C)
    for j in range(H + W):
        if (i >> j) & 1:
            if j < H:
                for k in range(W):
                    V[j][k] = "R"
            else:
                for k in range(H):
                    V[k][j - H] = "R"
    if sum(V, []).count("
        count += 1

print(count)

Solution (Python):
import numpy as np
from itertools import chain,combinations
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

H, W, K = map(int, input().split())
c = []
for h in range(H):
    c.append(list(map(str, input())))
c = np.array(c)


h_list = [i for i in range(H)]
w_list = [i for i in range(W)]

h_comb_list = list(powerset(h_list))
w_comb_list = list(powerset(w_list))



comb_list = []
x = 0
for h_temp in h_comb_list:
    for w_temp in w_comb_list:
        if -1 in h_temp and -1 in w_temp:
                x += 1
        else:
            comb_list.append({'h':h_temp, 'w':w_temp})
ans = 0
for comb in comb_list:
    h_r = comb['h']
    w_r = comb['w']
    h_temp = [i for i in range(H)]
    w_temp = [i for i in range(W)]
    
    if len(h_r) > 0:
        for h in h_r:
            h_temp.remove(h)
    if len(w_r) > 0:
        for w in w_r:
            w_temp.remove(w)
    
    if np.sum(c[h_temp, :][:, w_temp] == '
        
        
        ans += 1
print(ans)

Solution (Python):
import itertools
import copy

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

rows = []
for i in range(h + 1):
    rows += list(itertools.combinations(list(range(0, h)), i))

cols = []
for i in range(w + 1):
    cols += list(itertools.combinations(list(range(0, w)), i))

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

result = 0
for row in rows:
    for col in cols:
        temp = copy.deepcopy(data)
        for r in row:
            for j in range(w):
                temp[r][j] = 'r'
        for c in col:
            for i in range(h):
                temp[i][c] = 'r'
        count = 0
        for i in range(h):
            for j in range(w):
                if temp[i][j] == '
                    count += 1
        if count == k:
            result += 1

print(result)

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


def sum(table):
    t = 0
    for i in range(len(table)):
        for j in range(len(table[i])):
            t += table[i][j]
    return t


def main(input, print):
    h, w, K = map(int, input().split())
    table = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        s = list(input())
        for j in range(w):
            if s[j] == '
                table[i][j] = 1
    ht = []
    for i in range(h+1):
        for v in itertools.combinations(range(h), i):
            ht.append(v)
    wt = []
    for i in range(w+1):
        for v in itertools.combinations(range(w), i):
            wt.append(v)

    ans = 0
    for i in range(len(ht)):
        now = copy.deepcopy(table)
        for j in range(len(ht[i])):
            for k in range(w):
                now[ht[i][j]][k] = 0
        for j in range(len(wt)):
            now2 = copy.deepcopy(now)
            for k in range(len(wt[j])):
                for l in range(h):
                    now2[l][wt[j][k]] = 0
            if sum(now2) == K:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Solution (Python):
import copy

h, w, s = map(int, input().split())
li = [list(input()) for _ in range(h)]
ans = 0

for i in range(h):
    for j in range(w):
        if li[i][j] == '
            li[i][j] = 1
        else:
            li[i][j] = 0

cnt = 0

for i in range(2 ** h):
    for j in range(2 ** w):
        swicth1 = [0]*h
        swicth2 = [0]*w
        
        for k in range(h):
            for l in range(w):
                if ((i >> k) & 1):
                    swicth1[h - 1 - k] = 1

                if ((j >> l) & 1):
                    swicth2[w - 1 - l] = 1
        tmp = copy.deepcopy(li)
        
        for x in range(h):
            for y in range(w):
                if swicth1[x] == 1 or swicth2[y] == 1:
                    tmp[x][y] = 0
        cnt = 0
        for x in range(h):
            cnt += sum(tmp[x])
        
        if cnt == s:
            ans += 1
                
print(ans)

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

ans = 0
for bit in range(1 << H):
    drow = []
    for i in range(H):
        if (bit >> i) % 2 == 1:
            drow.append(i)
    for bit2 in range(1 << W):
        dcol = []
        for j in range(W):
            if (bit2 >> j) % 2 == 1:
                dcol.append(j)
        b = 0
        for y in range(H):
            for x in range(W):
                if y in drow:
                    continue
                if x in dcol:
                    continue
                if C[y][x] == "
                    b += 1
        if b == K:
            ans += 1
print(ans)

Solution (Python):
import numpy
import numpy
import itertools

H, W, K = map(int, input().split())
c = []
for _ in range(H):
    line = list(input().replace('.', '0').replace('
    c.append(line)

c = numpy.array(c, dtype = numpy.int)
ans = 0

for pi in itertools.product([0,1], repeat = H):
    for pj in itertools.product([0,1], repeat = W):
        Ii = numpy.array(pi) == 1
        Ij = numpy.array(pj) == 1
        d = c.copy()
        d[Ii, :] = 0
        d[:, Ij] = 0
        if numpy.sum(d) == K:
            ans += 1

print(ans)

Solution (Python):





def modinv(n,p):
    return pow(n,p-2,p)

from itertools import combinations

def main():
    
    

    n, m, k = [int(x) for x in input().split()]
    mat = [[0] * m for i in range(n)]
    for i in range(n):
        s = input()
        for j in range(m):
            if s[j] == '.':
                mat[i][j] = 1
    

    c = 0
    rows = [x for x in range(n)]
    cols = [x for x in range(m)]

    new_rows = []
    new_cols = []

    
    

    for i in range(2, n+1):
        temp = list(combinations(rows, i))
        
        for x in temp:
            new_rows.append(list(x))
    rows = [[x] for x in range(n)]
    for x in new_rows:
        rows.append(x)

    for i in range(2, m+1):
        temp = list(combinations(cols, i))
        
        for x in temp:
            new_cols.append(list(x))
    cols = [[x] for x in range(m)]
    for x in new_cols:
        cols.append(x)

    rows.append([])
    cols.append([])
    
    
    

    ans = 0
    
    for r in range(len(rows)):
        for c in range(len(cols)):
            new_mat = [[0] * m for x in range(n)]
            
            row = rows[r]
            col = cols[c]
            
            for i in range(n):
                for j in range(m):
                    if i in row or j in col:
                        new_mat[i][j] = 2
                    else:
                        new_mat[i][j] = mat[i][j]
            

            count_black = 0
            
            for x in new_mat:
                count_black += x.count(0)
            if count_black == k:
                ans += 1
            
            
            
            
    print(ans)


py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__ == '__main__':
   main()

Solution (Python):
import copy
import itertools

def delete_H(num, C_rend):
  lenj = len(num)
  if lenj != 0:
    for count in range(lenj):
      C_rend[j[count]] = "r" * W
  return(C_rend)

def delete_W(num, C_rend):
  lenl = len(num)
  if lenl != 0:
    for count in range(lenl):
      for i in range(H):
        c_h_list = list(C_rend[i])
        c_h_list[l[count]] = "r"
        C_rend[i] = "".join(c_h_list)
  return(C_rend)

H, W, K = map(int, input().split())
C = []
for i in range(H):
  add_H = map(str, input().split())
  C += add_H

counter = 0
C_orig = copy.deepcopy(C)  

for i in range(H + 1):
  for j in itertools.combinations(range(H), i):
    for k in range(W + 1):
      for l in itertools.combinations(range(W), k):
        C = copy.deepcopy(C_orig)
        modified_C_a = delete_H(j, C)
        modified_C_b = delete_W(l, modified_C_a)
        result = "".join(modified_C_b)
        
        if result.count("
          counter += 1
        
print(counter)

Solution (Python):

import sys,itertools
import numpy as np
input = sys.stdin.readline
h, w, k = map(int, input().split())
c_ = []
for i in range(h):
  cc = input().split()
  c_.append([0 if s=='.' else 1 for s in cc[0]])

c = np.array(c_)



h_s = []
for i in range(2**h):
  lis_h = []
  for j in range(h):
    if (i>>j) &1==1:
      lis_h.append(j)
  h_s.append(lis_h)
  
w_s = []
for i in range(2**w):
  lis_w = []
  for j in range(w):
    if (i>>j) &1==1:
      lis_w.append(j)
  w_s.append(lis_w)

count = 0


for hh in h_s:
  for ww in w_s:
    c_copy = c.copy()
    c_copy[hh,:]=0
    c_copy[:,ww]=0
    
    if np.sum(c_copy)==k:
      count+=1
print(count)

Solution (Python):
h, w, k = map(int,input().split())
import copy

def generate_n_bit(n):
    bins= []
    for i in range(2**n):
        bins.append(list(str(format(i,'b').zfill(n))))
    
    return bins

h_all = generate_n_bit(h)
w_all = generate_n_bit(w)
ans = 0
n = 23
extra = 1
  
for i in range(1,n+1): 
    extra = extra * i 

    
field = [list(input()) for i in range(h)]

for i_l in h_all:
    for j_l in w_all:
        c  = 0 
        fields = copy.deepcopy(field)
       
        
        for i_i, i in enumerate(i_l):
            for j_i, j in enumerate(j_l):
                n = 23
                extra = 1
  
                for xx in range(1,n+1): 
                    extra = extra * xx 
                if i == '1':
                    for a in range(w):
                        fields[i_i][a] = 'r'
                    
                if j == '1':
                    for b in range(h):
                
                        fields[b][j_i] = 'r'
                        
        
        for q in range(h):
            for e in range(w):
                if fields[q][e] == '
                    c += 1
       
        if c == k:
            ans += 1
        
n = 23
fact = 1
  
for i in range(1,n+1): 
    fact = fact * i         
                
print(ans)

Solution (Python):
import copy
H, W, K = map(int, input().split())
C = [list(input()) for _ in range(H)]
ans = 0
for i in range(1<<H):
  D = copy.deepcopy(C)
  for h in range(H):
    if (i>>h & 1):
      for l in range(W):
        D[h][l] = '.'
  for j in range(1<<W):
    k = 0
    for w in range(W):
      if not (j>>w & 1):
        for m in range(H):
          if D[m][w] == '
            k += 1
    if k == K:
      ans += 1
print(ans)

Solution (Python):
import copy
import itertools

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

field = []
for i in range(h):
  field.append(list(input()))
  
total = 0
for i in itertools.product([0,1], repeat=h):
  for j in itertools.product([0,1], repeat=w):
    count = 0
    temp = copy.deepcopy(field)
    for l in range(h):
      if i[l] == 1:
        temp[l] = ['.'] * w
    for l in range(w):
      if j[l] == 1:
        for m in range(h):
          temp[m][l] = '.'
    for l in range(h):
      count += temp[l].count('
    if count == k:
      total += 1
      
print(total)

Solution (Python):
h,w,k=map(int,input().split())
c=[]
for i in range(h):
    y=list(input())
    c.append(y)
s=0
for i in range(2**h):
    for j in range(2**w):
        t=0
        for a in range(h):
            for b in range(w):
                if (i//(2**a))%2==1 and (j//(2**b))%2==1 and c[a][b]=="
                    t+=1
        if t==k:
            s+=1
print(s)

Solution (Python):
H, W, K = map(int, input().split())
MAP = [list(input()) for i in range(H)]
Ho = [MAP[i].count('
Whole = sum(Ho)
count = 0

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

Ve = [ve(j) for j in range(W)]

def iter_p_adic(p, n):
    from itertools import product
    tmp = [range(p)] * n
    return product(*tmp)

ite_H = list(iter_p_adic(2, H))
ite_V = list(iter_p_adic(2, W))

for idx_H in ite_H:
    for idx_V in ite_V:
        count_double = 0
        count_minus = 0
        h = list(idx_H)
        v = list(idx_V)
        for k in range(W):
            if v[k] == 1:
                count_minus += Ve[k]
        
        for i in range(H):
            for j in range(W):
                if v[j] == 1 and h[i] == 1 and MAP[i][j] == '
                    count_double += 1
            if h[i] == 1:
                count_minus += Ho[i]
        if Whole - count_minus + count_double == K:
            count += 1

print(count)

Solution (Python):
from copy import copy

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

def draw_tate(c, i):
    
    for j in range(len(c)):
        c[j] = c[j][0:i] + "." + c[j][i+1:]
    

def draw_yoko(c, i):
    
    c[i] = "." * w
        

a = 0
b = 2 ** h 
e = 2 ** w 
for i in range(b):
    for j in range(e):
        d = copy(c)
        for m in range(h):
            if ((1 << m) & i) != 0:
                draw_yoko(d, m)
        for l in range(w):
            if ((1 << l) & j) != 0:
                draw_tate(d, l)
        d = ''.join(d)
        if d.count("
            a += 1
print(a)

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

total = list()
row = [0]*h
col = [0]*w

for i in range(h):
    wh = list(map(int,list(input().replace(".","0").replace("
    for j in range(w):
        col[j] += wh[j]
    row[i] = sum(wh)
    total.append(wh)

tc = sum(row)
ans = 0

for i in range(2**h):
    for j in range(2**w):
        tmp = list()
        cou = tc
        ti =i
        tj =j
        for th in range(h):
            if ti == 0:
                break
            if ti%2 == 1:
                cou -= row[th]
                tmp.append(th)
            ti = ti//2 
        for tw in range(w):
            if tj == 0:
                break
            if tj%2 == 1:
                cou -= col[tw]
                for hhh in tmp:
                    cou += total[hhh][tw]
            tj = tj//2
        if cou == k:
            ans += 1

print(ans)

Solution (Python):
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations, permutations
from heapq import heapify, heappush, heappop



n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

H, W, K = nn()
C = sl(H)
D = array2(H, W)

for i in range(H):
    for j in range(W):
        D[i][j] = 1 if C[i][j] == "

ans = 0
for n in range(2**H):
    for m in range(2**W):
        E = deepcopy(D)
        for i in range(H):
            if (n>>i) & 1 == 1:
                for k in range(W):
                    E[i][k] = 0

        for j in range(W):
            if (m>>j) & 1 == 1:
                for k in range(H):
                    E[k][j] = 0

        

        count = 0
        for i in range(H):
            for j in range(W):
                if E[i][j] == 1:
                    count += 1

        
        if count == K:
            
            ans += 1

        

print(ans)

Solution (Python):
from collections import Counter
from itertools import product

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


def cnt_black(lists):
    cnt = 0
    for lis in lists:
        cnt += Counter(lis).get('
    return cnt


def to_red(lists, row_ops, col_ops):
    lists = lists.copy()
    for idx in range(H):
        if row_ops[idx] == '1':
            lists[idx] = ['r'] * W
    for idx in range(W):
        if col_ops[idx] == '1':
            lists = [lis[:idx] + ['r'] + lis[idx + 1:] for lis in lists]
    return lists

row_patterns = [format(n, f'0{H}b') for n in range(2 ** H)]
col_patterns = [format(n, f'0{W}b') for n in range(2 ** W)]

cnt = 0
for row_ops, col_ops in product(row_patterns, col_patterns):
    red_lists = to_red(lists, row_ops, col_ops)
    if cnt_black(red_lists) == K:
        cnt += 1
print(cnt)

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

ans = 0
for bit1 in range(2**H):
    y_map = copy.deepcopy(c_map)
    for i in range(H):
        if bit1 & (1<< i):
            y_map[i] = np.where(y_map[i]!=1, ".", y_map[i])

    for bit2 in range(2**W):
        x_map = copy.deepcopy(y_map)
        for j in range(W):
            if bit2 & (1<< j):
                x_map[:,j] = np.where(x_map[:,j]!=1, ".", x_map[:,j])
        if np.count_nonzero(x_map == "
            ans += 1
print(ans)

Solution (Python):
def f(k):
    if k == 1:
        return [[0],[1]]
    else:
        h = f(k-1)
        h_plus = [hi + [0] for hi in h]
        h_minus = [hi + [1]for hi in h]
        return h_plus + h_minus

def count(select_h,select_w,hw):
    chw = hw.copy()
    count = 0
    for i,si in enumerate(select_h):
        for j,sj in enumerate(select_w):
            if not(si or sj):
                count += chw[i][j]
    return count

H,W,K = map(int,input().split( ))
hw = [list(str(input())) for _ in range(H)]
for h in range(H):
    for w in range(W):
        if hw[h][w] == '
             hw[h][w] = 1
        else:
            hw[h][w] = 0

select_hs = f(H)
select_ws = f(W)
ans = 0
for select_h in select_hs:
    for select_w in select_ws:
        if count(select_h,select_w,hw) == K:
            ans += 1
print(ans)

Solution (Python):


def resolve():
    import sys
    import numpy as  np
    input = sys.stdin.readline
    hwk = [int(x) for x in input().rstrip().split(" ")]
    h = hwk[0]
    w = hwk[1]
    k = hwk[2]
    matrix = np.zeros((h, w))

    for i in range(h):
        
        row = input().rstrip()
        for j in range(w):
            matrix[i, j] = 0 if row[j] == "." else 1
    
    import itertools
    ans = 1 if np.count_nonzero(matrix) == k else 0
    for n in range(1,h+w):
        for pair in itertools.combinations(list(range(h+w)), n):
            tmp = matrix.copy()
            
            
            for i in pair:
                if(i < h):
                    tmp[i, :] = 0
                else:
                    tmp[:, i-h] = 0
            
            if np.count_nonzero(tmp) == k:
                ans += 1
            
            
            
    print(ans)
        

        
            




if __name__ == "__main__":
    resolve()

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

def to_int(s):
    if s == ".":
        return 0
    else:
        return 1

c = [0] * H
for i in range(H):
    c[i] = list(map(to_int, input()))

res = 0
for h_bit in range(1<<H):
    for w_bit in range(1<<W):
        sum_c = 0
        h = h_bit
        for i in range(H):
            if h % 2 == 1:
                w = w_bit
                for j in range(W):
                    if w % 2 == 1:
                        sum_c += c[i][j]
                    w //= 2
            h //= 2
        if sum_c == K:
            res += 1
    
print(res)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def contBlack(g, h, w):
    cnt = 0
    for i in range(h):
        for j in range(w):
            if g[i][j] == '
                cnt += 1
    return cnt

def turnrow(g, a, w):
    for j in range(w):
        g[a][j] = 'R'



def turnclumn(g, a, h):
    for i in range(h):
        g[i][a] = 'R'

from copy import deepcopy

def main():
    H, W, K = map(int, readline().split())
    grid = []
    for _ in range(H):
        grid.append(list(input()))

    cnt = 0
    for i in range(1<<H):           
        G = deepcopy(grid)
        for j in range(H):
            if (i>>j) & 1:
                turnrow(G, j, W)

        for k in range(1<<W):
            Gg = deepcopy(G)
            for l in range(W):
                if (k>>l) & 1:
                    turnclumn(Gg, l, H)
            
            
            
            

            if contBlack(Gg, H, W) == K:
                cnt += 1

    print(cnt)
if __name__ == '__main__':
    main()

Solution (Python):
import itertools,copy
H,W,K=map(int,input().split())
c=[]
for i in range(H):
    c.append(list(input()))
tmp=copy.deepcopy(c)
ans=0
for i in itertools.product([0,1], repeat=H+W):
    c=copy.deepcopy(tmp)
    for j in range(H):
        if(i[j]==0):
            for k in range(W):
                c[j][k]="R"
    for j in range(H,H+W):
        if(i[j]==0):
            for k in range(H):
                c[k][j-H]="R"
    s=0
    for i in range(H):
        s+=c[i].count("
    if(s==K):
        ans+=1
print(ans)

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


h, w, k = map(int, input().split())
C = np.array([list(input()) for j in range(h)]) == "
out = 0

for row_n in range(h):
    for row_select in combinations(C, r=row_n + 1):
        
        for col_n in range(w):
            for col_select in combinations(zip(*row_select), r=col_n + 1):
                if np.array(col_select).sum() == k:
                    out += 1
print(out)

Solution (Python):
from itertools import combinations_with_replacement as cwr
H,W,K=map(int,input().split())
C=[]
for _ in range(H):
    c = list(map(str, input()))
    C.append(c)
ans=0
lh = [0 for _ in range(H)]
while True:    
    lw = [0 for _ in range(W)]
    while True:
        num =0
        for i in range(H):
            for j in range(W):
                if lh[i]==1 or lw[j]==1 or C[i][j]==".":
                    continue
                else:
                    num+=1
        if num==K:
            ans +=1
        if sum(lw)==W:
            break
        for k in range(W):
            if lw[k]==0:
                lw[k]=1
                break
            if lw[k]==1:
                lw[k]=0
    if sum(lh)==H:
        break
    for k in range(H):
        if lh[k]==0:
            lh[k]=1
            break
        elif lh[k]==1:
            lh[k]=0

print(ans)