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 itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue


Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
import string
def main():  
    h, w, K = map(int, input().split())
    cmat = [input() for i in range(h)]
    ans = 0
    sublist = []
    com_sublist = [] 
    
    firstblack = 0
    for i in range(h):
        firstblack += cmat[i].count("
    for i in range(1 << h):
        for j in range(h):
            if (i >> j) & 1:
                sublist.append(cmat[j])
            else:
                com_sublist.append(cmat[j])
        
        lensub = len(sublist)
        lencomsub = len(com_sublist)
        elecnt = 0
        for ele in sublist:
            elecnt += ele.count("
        
        
        newcomsub = []
        for j in range(w):
            newcomsub.append([com_sublist[k][j] for k in range(lencomsub)])
        
        for j in range(w):
            if not (newcomsub[j]):
                continue
            newcomsub[j] = "".join(newcomsub[j])
        subcomsub = []
        for j in range(1 << w):
            comelecnt = 0
            for k in range(w):
                if (j >> k) & 1:
                    subcomsub.append(newcomsub[k])
            
            for subele in subcomsub:
                comelecnt += subele.count("
            
            if firstblack - (elecnt + comelecnt) == K:
                ans += 1
            subcomsub = []
        
        sublist = []
        com_sublist = []

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
H, W, K = (int(i) for i in input().split())
C = np.zeros((H, W))
for h in range(H):
    C[h,:] = [int(i=='
res = 0
for i in range(2 ** H):
    for j in range(2 ** W):
        hv = np.array(list(format(i, '0{}b'.format(H))), dtype='int')
        wv = np.array(list(format(j, '0{}b'.format(W))), dtype='int')
        if C[hv==1,:][:, wv==1].sum() == K:
            res = res + 1
print(res)

Solution (Python):
import copy
from itertools import combinations
h, w, k = map(int, input().split())
c =[input() for i in range(h)]
ans = 0
y = []
for i in range(h):
    y.append(i)
x = []
for i in range(w):
    x.append(i)
for i in range(h+1):
    ty = list(combinations(y, i))
    for j in range(w+1):
        tx = list(combinations(x, j))
        for l in ty:
            for m in tx:
                cnt = 0
                for p in l:
                    for q in m:
                        if c[p][q] == '
                            cnt += 1
                if cnt == k:
                    ans += 1
print(ans)

Solution (Python):
import numpy as np
import itertools
H, W, K = map(int, input().split())
L = np.array([list(input()) for i in range(H)])
Ans = 0
for h in range(H):
    for w in range(W):
        if L[h,w] == '.':
            L[h,w] = '0'
        else:
            L[h,w] = '1'
L = L.astype("int64")

def del_w(w):
    if w != 0:
        for h1 in range(H):
            L1[h1,w-1] =  0   

def del_h(h):
    if h != 0:
        for w1 in range(W):
            L1[h-1,w1] =  0
            
H_list = []
for h in range(H+1):
    H_list += list(itertools.combinations(range(1,H+1),h))

W_list = []
for w in range(W+1):
    W_list += list(itertools.combinations(range(1,W+1),w))
    
for h_list in H_list:
    for w_list in W_list:
        
        L1 = L.copy()
        
        for w1 in w_list :
            for h in range(H):
                L1[h,w1-1] =  0
                
        for h1 in h_list :
            for w in range(W):
                L1[h1-1,w] =  0 
                
        if np.sum(L1) == K:
            
            Ans += 1
            
print(Ans)

Solution (Python):

import itertools

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

l1 = [i for i in range(H)]
l2 = [i for i in range(W)]

ans = 0
for i in range(H + 1):
    p1 = list(itertools.combinations(l1, i))
    for j in p1:
        for k in range(W + 1):
            p2 = list(itertools.combinations(l2, k))
            for l in p2:
                cnt = 0
                for m in range(H):
                    for n in range(W):
                        if (m not in list(j) and n not in list(l) and lst[m][n] == '
                            cnt += 1
                if (cnt == K):
                    ans += 1
print(ans)

Solution (Python):

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

    total = 0

    for bit_h in range(2 ** H):
        for bit_w in range(2 ** W):
            check_board = [[True for _ in range(W)] for _ in range(H)]
            for h_cheker in range(H):
                if (bit_h >> h_cheker) & 1:
                    for temp_w in range(W):
                        check_board[h_cheker][temp_w] = False
            for w_checker in range(W):
                if (bit_w >> w_checker) & 1:
                    for temp_h in range(H):
                        check_board[temp_h][w_checker] = False
            counter = 0
            for h in range(H):
                for w in range(W):
                    if check_board[h][w] and board[h][w] == "
                        counter += 1

            if counter == K:
                total += 1

    print(total)




if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

H,W,K=map(int,input().strip().split())
c=[]
for n in range(H):
    c.append(list(input()))
for h in range(H):
    for w in range(W):
        if c[h][w]==".":
            c[h][w]=0
        else:
            c[h][w]=1
c=np.array(c)

cnt=0
def rec(l,H,W,K):
    global cnt
    if len(l)==H+W:
        t=c.copy()
        for i in range(len(l)):
            if i<=H-1:
                if l[i]==1:
                    t[i,:]=0
            else:
                if l[i]==1:
                    t[:,i-H]=0
        if np.sum(t)==K:
            cnt+=1
    else:
        for n in range(2):
            l.append(n)
            rec(l,H,W,K)
            l.pop()

rec([],H,W,K)
print(cnt)

Solution (Python):
import copy
H,W,K=map(int,input().split())
List = []
for i in range (H):
  List.append(list((input())))
res = 0
List2 = copy.deepcopy(List)
List3 = copy.deepcopy(List)

                   
def checkBlack(listA, check):
  inter =0
  for k in range(H):
    inter += listA[k].count("
  if check == inter:
    return True
  else:
    return False
  

def paintH(listB,k):
  for i in range(H):
    listB[i][k] = 0
  return listB


def paintW(listB,k):
  for i in range(W):
    listB[k][i] = 0
  return listB

for bits in range(2**W):
  for j in range(W):
    if((bits>>j) & 1): 
      List3 = paintH(List2,j)
  List4 = copy.deepcopy(List3)  
  for bits2 in range(2**H):
    for l in range(H):
      if((bits2>>l) & 1): 
        List2 = paintW(List4,l)
    if checkBlack(List4,K):
      res +=1
    List4 = copy.deepcopy(List3)
  List2 = copy.deepcopy(List)
print(res)

Solution (Python):
import copy
H, W, K = map(int,input().split())
c = [list(input()) for j in range(H)]
c_tmp =copy.deepcopy(c)


w_combs =[]
for i in range(2**W):
  w_comb = []
  for j in range(W):
    if (i >>j) & 1 :
      w_comb.append(j)
  w_combs.append(w_comb)

h_combs = []
for i in range(2**H):
  h_comb = []
  for j in range(H):
    if (i >>j) & 1 :
      h_comb.append(j)
  h_combs.append(h_comb)


ans = 0

for h_comb in h_combs:
  for w_comb in w_combs:
    c_tmp =copy.deepcopy(c)


    for w_one in w_comb:
      for y in range(H):
        c_tmp[y][w_one] = 'r'
    
    for h_one in h_comb:
      for x in range(W):
        c_tmp[h_one][x] = 'r'
    

    cnt_black = 0
    for row in c_tmp:
      for c_i in row:
        if c_i == '
          cnt_black +=1

    if cnt_black == K:
      ans +=1

print(ans)

Solution (Python):
from itertools import product
inpl = lambda: list(map(int,input().split()))
H, W, K = inpl()
c = [input() for _ in range(H)]

ans = 0
for p in product(range(2),repeat=H):
    for q in product(range(2),repeat=W):
        num = 0
        for h in range(H):
            if p[h]:
                continue
            for w in range(W):
                if q[w]:
                    continue
                if c[h][w] == '
                    num += 1
                    if num > K:
                        break
            else:
                continue
            break
        else:
            if num == K:
                ans += 1
print(ans)

Solution (Python):
import numpy as np

H,W,K=map(int,input().split())
C=[]
for _ in range(H):
    c=input()
    a=[b for b in c]
    C.append(a)

answer=0

C=tuple(C)
A=[]

hs=[]
ws=[]
suuji=[i for i in range(H)]
for i in range(2 ** H):
  skill=[]
  for j in range(H):
    if ((i >> j) & 1):
        skill.append(suuji[j])
  hs.append(skill)
del hs[0]
suuji=[i for i in range(W)]
for i in range(2 ** W):
  skill=[]
  for j in range(W):
    if ((i >> j) & 1):
        skill.append(suuji[j])
  ws.append(skill)
del ws[0]

suuji=0
for h in hs:
    for w in ws:
        number=0
        D=np.array(C)
        for h_ in h:
            D[h_,:]=0
        for w_ in w:
            D[:,w]=0
        for c in D:
            for c_ in c:
                if c_=='
                    number+=1
        if number==K:
            answer+=1
for h in hs:
    number=0
    D=np.array(C)
    for h_ in h:
        D[h_,:]=0

    for c in D:
        for c_ in c:
            if c_=='
                number+=1
    if number==K:
        answer+=1
for h in ws:
    number = 0
    D = np.array(C)
    for h_ in h:
        D[:, h_] = 0

    for c in D:
        for c_ in c:
            if c_ == '
                number += 1
    if number == K:
        answer += 1

number=0
D=np.array(C)
for d in D:
    for d_ in d:
        if d_=='
            number+=1
if number==K:
    answer+=1

print(answer)

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

def blk_counter(mat):
    cnt = np.count_nonzero(mat == '
    return cnt


def main():
    H, W, K = map(int,input().split(' '))
    r_index = [i for i in range(H)]
    c_index = [i for i in range(W)]
    mat = []
    for i in range(H):
        mat.append(list(input()))
    
    mat = np.array(mat)

    blk_cnt = 0
    cnt = 0

    dele_r_list = []
    dele_c_list = []

    for i in range(H+1):
        for j in combinations(r_index,i):
            dele_r_list.append(j)

    for i in range(W+1):
        for j in combinations(c_index,i):
            dele_c_list.append(j)

    for deler in dele_r_list:
        mat_d = np.delete(mat, deler, 0)
        for delec in dele_c_list:
            mat_dd = np.delete(mat_d, delec, 1)
            blk_cnt = blk_counter(mat_dd)
            if blk_cnt == K:
                cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
import copy
h,w,k = map(int,input().split())
c= [[0] * w for i in range(h)]
for i in range(h):
  l = list(input())
  for j in range(w):
    if l[j]=="
      c[i][j]=1
cc = 0
for bit in range(2**(h+w)):
  temp = copy.deepcopy(c)
  for i in range(h):
    if ((bit >> (i+w)) & 1):
      temp[i][:]=[0]*w
  for j in range(w):
    if ((bit >> j) & 1):
      for i in range(h):
        temp[i][j]=0
  temp_c = 0
  for i in range(h):
    for j in range(w):
      if temp[i][j]==1 : temp_c+=1
  if temp_c==k : cc+=1
print(cc)

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

hlst = [0] * H
wlst = [0] * W
looph = []
loopw = []
def dfs(cnt, lst, loop):
    if cnt == len(lst):
        loop.append(copy.deepcopy(lst))
        return
    for i in range(2):
        lst[cnt] = i
        cnt += 1
        dfs(cnt, lst, loop)
        cnt -= 1

dfs(0, hlst, looph)
dfs(0, wlst, loopw)

total = 0
for i in looph:
    for j in loopw:
        cnt = 0
        for k in range(H):
            for l in range(W):
                if i[k] == 1:
                    continue
                if j[l] == 1:
                    continue
                if c[k][l] == '
                    cnt += 1

        if cnt == K:
            total += 1

print(total)

Solution (Python):

import itertools
import numpy as np

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

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

c_rep = c.copy()
for i in range(h):
    for j in range(w):
        if c[i][j] == ".":
            c_rep[i][j] = 0
        else:
            c_rep[i][j] = 1
c = np.array(c_rep)

hp = [""] * (h+1)
for i in range(1,h+1):
    hp[i] = list(itertools.combinations(range(h), i))

hp_lis = [[]]
for i in range(len(hp)):
    if i == "":
        hp_lis.append([])
    else:
        for j in range(len(hp[i])):
            hp_lis.append(list(hp[i][j]))

wp = [""] * (w+1)
for i in range(1,w+1):
    wp[i] = list(itertools.combinations(range(w), i))

wp_lis = [[]]
for i in range(len(wp)):
    if i == "":
        wp_lis.append([])
    else:
        for j in range(len(wp[i])):
            wp_lis.append(list(wp[i][j]))

count = 0
for i in range(len(hp_lis)):
    for j in range(len(wp_lis)):
        
        temp = np.delete(c, obj=hp_lis[i], axis=0)
        temp = np.delete(temp, obj=wp_lis[j], axis=1)
        
        if np.sum(temp) == k:
            count += 1

print(count)

Solution (Python):
import itertools

[H,W,K] = list(map(int,input().split()))
count=0

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



ini=0
for i in range(H):
    for j in range(W):
        if c[i][j]=='
            ini+=1




a = [0,1]
Gs = list(itertools.product(a, repeat=H))
Rs = list(itertools.product(a, repeat=W))

for G in Gs:
    for R in Rs:
        
        l=0
        gyo=0
        for i in G:
            if i==1:
                
                gyo+= c[l].count('
            l+=1
        

        
        r=0
        retu=0
        for j in R:
            if j==1:
                
                for k in range(H):
                    
                    if c[k][r]=='
                        retu+=1
            r+=1
        

        
        iii=0
        hiku=0
        for ii in G:
            jjj=0
            for jj in R:
                if ii==1 and jj==1:
                    if c[iii][jjj]=='
                        hiku+=1
                jjj+=1
            iii+=1
        

        if ini - (gyo+retu-hiku)==K:
            count+=1
        


print(count)

Solution (Python):
import copy

H, W, K = map(int, input().split())
ll = [[0 for w in range(W)] for h in range(H)]
ans = 0

for h in range(H):
  row = input()
  for w in range(W):
    if (row[w] == '.'):
      ll[h][w] = 0
    else:
      ll[h][w] = 1

for h in range(2 ** H):
  hstr = format(h, f'0{H}b')
  for w in range(2 ** W):
    wstr = format(w, f'0{W}b')
    l = copy.deepcopy(ll)
    count = 0
    for h1 in range(H):
      for w1 in range(W):
        if (hstr[h1] == '1' or wstr[w1] == '1'):
          l[h1][w1] = 0
        count += l[h1][w1]
    if (count == K):
      ans += 1

print(ans)

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

hlst = [0] * H
wlst = [0] * W
looph = []
loopw = []
def dfs(cnt, lst, loop):
    if cnt == len(lst):
        loop.append(copy.deepcopy(lst))
        return
    for i in range(2):
        lst[cnt] = i
        cnt += 1
        dfs(cnt, lst, loop)
        cnt -= 1

dfs(0, hlst, looph)
dfs(0, wlst, loopw)

total = 0
for i in looph:
    for j in loopw:
        cnt = 0
        for k in range(H):
            for l in range(W):
                if i[k] == 1:
                    continue
                if j[l] == 1:
                    continue
                if c[k][l] == '
                    cnt += 1

        if cnt == K:
            total += 1

print(total)

Solution (Python):
import copy
s=0
a=0
H,W,K=map(int,input().split())
L=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
  c=list(input())
  L[i]=c
for i in range(2**(H+W)):
  c=bin(i)[2:]
  c=str(c)
  if len(c)<H+W:
    c=str((H+W-len(c))*"0"+c)
  T=copy.deepcopy(L)
  for k in range(H+W):
    if c[k]=="1":
      if k<H:
        T[k]=[0]*W
    if c[k]=="1" and k>=H:
      for n in range(H):
        T[n][k-H]=0
  for j in range(1,(H*W)+1):
    if j%W==0:
      if T[(j//W)-1][-1]=="
        a+=1
    else:
      if T[j//W][(j%W)-1]=="
        a+=1
  if a==K:
    s+=1
  a=0
print(s)

Solution (Python):
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

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

    res = 0

    for h in list(product([0, 1], repeat=H)):
        for w in list(product([0, 1], repeat=W)):
            hash_count = 0
            for row in range(H):
                if h[row]:
                    continue
                else:
                    for col in range(W):
                        if C[row][col] == '
                            hash_count += 1
            
            if hash_count == K:
                res += 1
    
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
h,w,k=map(int,input().split())
l=[input()for _ in range(h)]
def t(m,h,w):
    n=[]
    for i in range(w):
        s=''
        for j in range(h):
            s+=m[j][i]
        n.append(s)
    return n
ans=0
for i in range(2**h):
    m=l.copy()
    b=bin(i)[2:].zfill(h)
    for n,i_ in enumerate(b):
        if i_=='1':
            m[n]='x'*w
    m=t(m,h,w)
    for j in range(2**w):
        x=m.copy()
        b=bin(j)[2:].zfill(w)
        for n,j_ in enumerate(b):
            if j_=='1':
                x[n]='x'*h
        c=0
        for r in x:
            c+=r.count('
        if c==k:
            ans+=1
print(ans)

Solution (Python):
import itertools

def bit(n, k):
    s = [0 for _ in range(k)]
    u = n
    b = 0
    while(u > 0):
        s[k-1-b] += u % 2
        u = u // 2
        b += 1
    return s

h, w, k = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())
    
tate = [0 for _ in range(w)]
yoko = [0 for _ in range(h)]
for i in range(w):
    for j in range(h):
        if(c[j][i] == "
            tate[i] += 1
for i in range(h):
    yoko[i] += c[i].count("
m = sum(yoko)

ans = 0
for i in range(2**h):
    for j in range(2**w):
        g = m
        comb_s = bit(i, h)
        comb_t = bit(j, w)
        for p in range(h):
            if(comb_s[p] == 1):
                g -= yoko[p]
        for q in range(w):
            if(comb_t[q] == 1):
                g -= tate[q]
        for p in range(h):
            for q in range(w):
                if(c[p][q] == "
                    g += 1
        if(g == k):
            ans += 1
print(ans)

Solution (Python):
h, w, k = map(int,input().split())
c = []
for i in range(h):
    r = []
    s = input()
    for j in s:
        if j == '.':
            r.append(0)
        else:
            r.append(1)
    c.append(r)

ans = 0

from copy import deepcopy
import numpy as np

for b in range(2**(h+w)):
    m = deepcopy(c)
    key = bin(b)[2:].zfill(h+w)
    for row in range(h):
        if key[:h][row] == '1':
            for col in range(w):
                m[row][col] = 0
    for col in range(w):
        if key[h:][col] == '1':
            for row in range(h):
                m[row][col] = 0
    if np.sum(m) == k:
        ans += 1

print(ans)

Solution (Python):
import itertools

H, W, K = map(int, input().split())
c = [['.' for j in range(6)] for i in range(6)]
for i in range(H):
    tmp = str(input())
    for j in range(len(tmp)):
        c[i][j] = tmp[j]
    
hp = list(itertools.product([0,1], repeat=H))
wp = list(itertools.product([0,1], repeat=W))

hl = []
for elem in hp:
    hl.append([i for i, x in enumerate(list(elem)) if x == 1])
wl = []
for elem in wp:
    wl.append([i for i, x in enumerate(list(elem)) if x == 1])

def func(hli, wli, c):
    tmp = 0
    for i in range(len(hli)):
        for j in range(len(wli)):
            if c[hli[i]][wli[j]] == '
                tmp += 1 
            
    return tmp

ans  = 0
for hli in hl:
    for wli in wl:
        if func(hli, wli, c) == K:
            ans += 1

print(ans)

Solution (Python):
import itertools
H, W, K = map(int, input().split())
Array = [[0]*W for _ in range(H)]

for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "
            Array[i][j] = 1
LH = range(H)
LW = range(W)
CH = []
CW = []
Ans = 0
for i in range(H+1):
    for combi in itertools.combinations(LH, i):
        CH.append(list(combi))
for i in range(W+1):
    for combi in itertools.combinations(LW, i):
        CW.append(list(combi))
for ch in CH:
    for cw in CW:
        Sum = 0
        for i in range(H):
            for j in range(W):
                if not (i in ch or j in cw):
                    Sum += Array[i][j]
        if Sum == K:
            Ans += 1
print(Ans)

Solution (Python):
import copy
from itertools import combinations
h, w, k = map(int, input().split())
c =[input() for i in range(h)]
ans = 0
y = []
for i in range(h):
    y.append(i)
x = []
for i in range(w):
    x.append(i)
for i in range(h+1):
    ty = list(combinations(y, i))
    for j in range(w+1):
        tx = list(combinations(x, j))
        for l in ty:
            for m in tx:
                cnt = 0
                for p in l:
                    for q in m:
                        if c[p][q] == '
                            cnt += 1
                if cnt == k:
                    ans += 1
print(ans)

Solution (Python):
import itertools
import copy

H,W,K = map(int,input().split())
Map = []
for i in range(H):
  c = list(input())
  tmp = []
  for j in range(W):
    if(c[j] == '.'): tmp.append(0)
    else: tmp.append(1) 
  Map.append(tmp)
  


A = list(itertools.product([0,1],repeat=H))
B = list(itertools.product([0,1],repeat=W))

ans = 0
for a_l in A:
  for b_l in B:
    tmp_Map = copy.deepcopy(Map)
    
    for a in range(len(a_l)):
      if(a_l[a] == 1):
        
        for j in range(W):
         tmp_Map[a][j] = 0
        
    for b in range(len(b_l)):
      if(b_l[b] == 1):
        
        for i in range(H):
         tmp_Map[i][b] = 0
        
    
    tmp = 0
    for i in range(H):
      tmp += sum(tmp_Map[i])
      
    if(tmp == K):
      ans += 1

print(ans)

Solution (Python):
H, W, K = map(int, input().split())
lists = [input() for i in range(H)]
black, ans = 0, 0
tate, yoko = [0 for i in range(H)],  [0 for i in range(W)]
listskai = [[0 for j in range(W)]for i in range(H)]

for i in range(W):
    for j in range(H):
        if lists[j][i] == '
            black += 1
            tate[j] += 1
            yoko[i] += 1
            listskai[j][i] = 1

def tmp(times, num, max, lista, numa):
    if times == 0:
        return lista + [num]

    for tmpi in range(numa + 1, max):
        if tmpi not in num:
            lista = tmp(times - 1, num + [tmpi], max, lista, tmpi)
    return lista

kurono = black

for looph in range(H):
    for j in tmp(looph, [], H, [], -1):
        for loopw in range(W):
            for i in tmp(loopw, [], W, [], -1):
                kurono = black
                for k in i:
                    kurono -= yoko[k]
                    for d in j:
                        kurono += listskai[d][k]

                for d in j:
                    kurono -= tate[d]

                if kurono == K:
                    ans += 1

print(ans)

Solution (Python):
import copy

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

    ans = 0

    for bitH in range(2**(H) - 1):
        for bitW in range(2**(W) - 1):
            Ctmp = copy.deepcopy(C)
            for i in range(H):
                if((bitH >> i) & 1):
                    Ctmp[i] = ["x" for _ in range(W)]
            Ctmp_t = [list(x) for x in zip(*Ctmp)]
            
            for j in range(W):
                if((bitW >> j) & 1):
                    Ctmp_t[j] = ["x" for _ in range(H)]
            
            Clast = [list(x) for x in zip(*Ctmp_t)]
            
            cnt = 0
            
            for s in range(H):
                cnt += Clast[s].count("
            
            if cnt == K:
                ans += 1
            
            

            
            
            
    print(ans)

solve()

Solution (Python):
import itertools
h, w, k = map(int, input().split())
field = []
for i in range(h):
  field.append(list(input()))
  
hb = [0 for i in range(h)]
wb = [0 for j in range(w)]
slist = []
tlist = []
bl = 0
ans = 0

for i in range(h):
  for j in range(w):
    if field[i][j] == "
      hb[i] += 1
      wb[j] += 1
      bl += 1

for i in range(h):
  for s in itertools.combinations(range(h), i):
    tmp = 0
    for es in s:
      tmp += hb[es]
    slist.append([list(s), tmp])
    
for j in range(w):
  for t in itertools.combinations(range(w), j):
    tmp = 0
    for et in t:
      tmp += wb[et]
    tlist.append([list(t), tmp])

    
for s in slist:
  for t in tlist:
    tmp = s[1] + t[1]
    if s and t:
      for es in s[0]:
        for et in t[0]:
          if field[es][et] == "
            tmp -= 1
    if bl - tmp == k:
      ans += 1
      
print(ans)

Solution (Python):
from itertools import *
import numpy as np
H,W,K = map(int,input().split())
C = [list(input()) for h in range(H)]
D = np.zeros((H,W),dtype=np.int)
a = 0

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

T = np.sum(D)

for h in range(1+H):
  for I in combinations(range(H),h):
    for w in range(1+W):
      for J in combinations(range(W),w):
        S = 0
        
        for i in I:
          for w in range(W):
            S+=D[i][w]
        for j in J:
          for h in range(H):
            S+=D[h][j]
        for i in I:
          for j in J:
            S-=D[i][j]
        
        if K==T-S:
          a+=1

print(a)

Solution (Python):
import numpy as np
H, W, K = map(int, input().split())
c = []
for i in range(H):
  s = str(input())
  l = [0 if t=='.' else 1 for t in s]
  c.append(l)
c = np.array(c)

ans = 0
tmp = c
for i in range(2**H-1):
  for j in range(H):
    if i >> j & 1:
      tmp[j] = 0
  tm = tmp
  for a in range(2**W-1):
    for b in range(W):
      if a >> b & 1:
        tmp[:, b] = 0
    t = np.sum(tmp)
    if t == K:
      ans += 1
    tmp = np.array(tm)
  tmp = np.array(c)
print(ans)

Solution (Python):
import itertools

H, W, K = map(int, input().split())
c = [['.' for j in range(6)] for i in range(6)]
for i in range(H):
    tmp = str(input())
    for j in range(len(tmp)):
        c[i][j] = tmp[j]
    
hp = list(itertools.product([0,1], repeat=H))
wp = list(itertools.product([0,1], repeat=W))

hl = []
for elem in hp:
    hl.append([i for i, x in enumerate(list(elem)) if x == 1])
wl = []
for elem in wp:
    wl.append([i for i, x in enumerate(list(elem)) if x == 1])





def func(hli, wli, c):
    tmp = 0
    for i in range(len(hli)):
        for j in range(len(wli)):
            if c[hli[i]][wli[j]] == '
                tmp += 1 
            
    return tmp


ans  = 0
for hli in hl:
    for wli in wl:
        if func(hli, wli, c) == K:
            ans += 1


print(ans)

Solution (Python):
h, w, k = map(int, input().split())
l = []
total = 0

for _ in range(h):
    c = list(input())
    total += c.count('
    l.append(c)
    
ans = 0
for i in range(2**h):
    count1 = 0
    li = []
    for j in range(h):
        if ((i>>j)&1):
            li.append(j)
            count1 += l[j].count('
    for a in range(2**w):
        count2 = 0
        for b in range(w):
            if ((a>>b)&1):
                for z in li:
                    if l[z][b] == "
                        count2 -= 1
                for c in range(h):
                    if l[c][b] == "
                        count2 += 1
        if total - count1 - count2 == k:
          ans += 1
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
c = [list(input()) for _ in range(H)]
digit = H + W
sum_b = 0
for x in c:
    sum_b += x.count('

brack = []
for i in range(H):
    for j in range(W):
        if c[i][j] == '
            brack.append(int(str(10**(H+j)+10**i).zfill(digit), 2))

ans = 0
for i in range(2**digit):
    tmp = 0
    for j in brack:
        if i & j != 0: tmp += 1
    if sum_b - tmp == K: ans += 1    
print(ans)