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.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, K = map(int, readline().split())
grid = [list(readline().decode().rstrip()) for _ in range(H)]
black_cnt = 0
a = [0]*H
b = [0]*W
for i in range(H):
  for j in range(W):
    if grid[i][j] == '
      a[i] += 1
      b[j] += 1
      black_cnt += 1
if black_cnt < K:
  print(0)
  sys.exit()
erase_cnt = black_cnt-K
N = H+W
ans = 0
for bit in range(1 << N):
    cnt = 0
    tmp_a = []
    tmp_b = []
    for i in range(N):
        if (bit >> i) & 1:       
            if i < H:
                tmp_a.append(i)
                cnt += a[i]
            else:
                tmp_b.append(i-H)
                cnt += b[i-H]
    for j in range(len(tmp_a)) :
        for k in range(len(tmp_b)):
            if grid[tmp_a[j]][tmp_b[k]] == '
                 cnt -= 1
    if cnt == erase_cnt:
        ans +=1
print(ans)

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

def judge(H_ex,W_ex):
    cp_array=copy.deepcopy(board)
    for i in range(H):
        for j in range(W):
            if H_ex&(2**i)!=0:
                cp_array[i][j]=2
    for j in range(W):
        for i in range(H):
            if W_ex&(2**j)!=0:
                cp_array[i][j]=2
    count=0
    for i in range(H):
        for j in range(W):
            if cp_array[i][j]==1:
                count+=1
    if count==K:
        return True
    else:
        return False


for i in range(H):
    input_str=input()
    board.append([])
    for j in range(W):
        v=0
        if input_str[j]=="
            v=1
        board[i].append(v)

H_cmb=2**H
W_cmb=2**W
count=0

for i in range(H_cmb):
    for j in range(W_cmb):
        if judge(i,j)==True:
            count+=1



print("{}".format(count))

Solution (Python):
import numpy as np

H, W, K = input().split(' ')
H = int(H)
W = int(W)
K = int(K)
c = [list(str(input())) for i in range(H)]
cnp = np.array(c)

countAll = np.count_nonzero(cnp == '
countH = []
countW = []
for i in range(H):
    countH.append(np.count_nonzero(cnp[i] == '
for i in range(W):
    countW.append(np.count_nonzero(cnp[:, i] == '

ans = 0
for i in range(2 ** H - 1):
    for j in range(2 ** W - 1):
        tmp = countAll
        tmp2 = []
        choiceH = format(i, '0' + str(H) + 'b')
        for m in range(len(choiceH)):
            if int(choiceH[m]):
                tmp -= countH[m]
                tmp2.append(m)
        choiceW = format(j, '0' + str(W) + 'b')
        for n in range(len(choiceW)):
            if int(choiceW[n]):
                tmp -= countW[n]
                for o in range(len(tmp2)):
                    if cnp[tmp2[o], n] == '
                        tmp += 1
        if tmp == K:
            ans += 1

print(ans)

Solution (Python):
from itertools import product, combinations
from copy import deepcopy


def main():
    H, W, K = (int(x) for x in input().split(" "))
    sqr = [list(input()) for _ in range(H)]
    
    cnt_black = sum([len([y for y in x if y == "
    cnt_way = 0
    for h in range(H+1):
        for w in range(W+1):
            for h_cs in combinations(range(H), h):
                for w_cs in combinations(range(W), w):
                    mask_sqr = deepcopy(sqr)
                    cnt_masked = 0
                    if len(h_cs) == 0:
                        for w_c in w_cs:
                            for i in range(len(sqr)):
                                if mask_sqr[i][w_c] == "
                                    mask_sqr[i][w_c] = "r"
                                    cnt_masked += 1
                    elif len(w_cs) == 0:
                        for h_c in h_cs:
                            for i in range(len(sqr[h_c])):
                                if mask_sqr[h_c][i] == "
                                    mask_sqr[h_c][i] = "r"
                                    cnt_masked += 1

                    else:
                        for h_c in h_cs:
                            for w_c in w_cs:
                                for i in range(len(sqr[h_c])):
                                    if mask_sqr[h_c][i] == "
                                        mask_sqr[h_c][i] = "r"
                                        cnt_masked += 1
                                for i in range(len(sqr)):
                                    if mask_sqr[i][w_c] == "
                                        mask_sqr[i][w_c] = "r"
                                        cnt_masked += 1

                    if cnt_black-cnt_masked == K:
                        cnt_way += 1
    print(cnt_way)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


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

HC=np.zeros(H)
WC=np.zeros(W)

for i in range(H):
  HC[i]=np.count_nonzero(B[i]==1)

for j in range(W):
  WC[j]=np.count_nonzero(B[:,j]==1)
WC=np.argsort(WC)
HC=np.argsort(HC)
count=0
for i in range(2 ** H):
  BB=B.copy()
  for iii in range(H):
    if [int(ii) for ii in list('{:06b}'.format(i))][6-H:][iii]==1:
      BB[iii]=1
  for j in range(2 ** W):
    BBB=BB.copy()
    for jjj in range(W):
      if [int(jj) for jj in list('{:06b}'.format(j))][6-W:][jjj]==1:
        BBB[:,jjj]=1
    if np.count_nonzero(BBB==0)==K:
      count+=1
print(count)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7



h, w, k = LI()
ans = 0
C = SR(h)
for hbit in range(2 ** h):
    for wbit in range(2 ** w):
        ret = 0
        for hi in range(h):
            for wi in range(w):
                if (hbit >> hi & 1) and (wbit >> wi & 1) and C[hi][wi] == "
                    ret += 1
        if ret == k:
            ans += 1



print(ans)

Solution (Python):
H, W, K = map(int, input().split())
lis =[]
for i in range(H):
    a =[]
    k = input()
    for j in range(W):
        if k[j]==".":
            lis.append(0)
        else:
            lis.append(1)
ans = 0
from itertools import product
import copy
one = list(product([False,True],repeat=H))
two = list(product([False,True],repeat=W))
for i in one:
    for j in two:
        target = copy.copy(lis)
        t = 0
        s = 0
        for k in i:

            if k == True:
                for l in range(W):
                    target[t+l] =0
            t += W
        for m in j:

            if m == True:
                for n in range(H):
                    target[s + n*W]=0
            s += 1
        if target.count(1) == K:
            ans+=1

print(ans)

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

graph = []
for h in range(H):
  graph.append(list(input()))

answer = 0

for choices in range(2 ** (W+H)):
  
  graph_copy = [ [0]*W for i in range(H)]
  for r in range(H):
    for c in range(W):
      graph_copy[r][c] = graph[r][c] 
  
  selected_rows = []
  selected_cols = []
  for i in range(W+H):
    if ((choices >> i) & 1):
      
      if (i < H):
        row = i
        selected_rows.append(row)
      
      else:
        col = i - H
        selected_cols.append(col)
  
  
  for row in selected_rows:
    for col in range(W):
      graph_copy[row][col] = "."
  for col in selected_cols:
    for row in range(H):
      graph_copy[row][col] = "."
  
  count = 0
  for r in range(H):
    for c in range(W):
      if (graph_copy[r][c] == "
        count += 1
  if (count == K):
    answer += 1
    
    
print(answer)

Solution (Python):
import itertools as it
h,w,k = map(int, input().split())
a,b,c,d = [],[],[],[]
for i in range(h):
    a.append(i)
for i in range(1,h+1):
    b += it.combinations(a,i)
for i in range(w):
    c.append(i)
for i in range(1,w+1):
    d += it.combinations(c,i)
board = [str(input()) for i in range(h)]
ans = 0
for i in b:
    for j in d:
        sh = 0
        for m in i:
            for l in j:
                if board[m][l] == '
                    sh += 1
        if sh == k:
            ans += 1
print(ans)

Solution (Python):
from copy import deepcopy

def color(c,h,w):
    if len(h) != 0:
        for i in h:
            for j in range(W):
                c[i][j] = 'R'

    if len(w) != 0:
        for i in w:
            for j in range(H):
                c[j][i] = 'R'

    return c

def cunt(c):
    tot = 0
    for i in range(H):
        for j in range(W):
            if c[i][j] == "
                tot+=1
    return tot

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

ans = 0

for i in range(2 ** H):
    for j in range(2 ** W):
        h = []
        w = []
        for  k in range(H):
            if ((i>>k) & 1):
                h.append(k)
        for k in range(W):
            if ((j >> k) & 1):
                w.append(k)
        _copy = deepcopy(c)
        tmp = color(_copy,h,w)
        
            
        _cunt = cunt(tmp)
        
        if _cunt == K:
            ans+=1

print(ans)

Solution (Python):
h,w,k = map(int,input().split())
c = [[0]*w for _ in range(h)] 
for i in range(h):
    f = input()
    for j in range(w):
        if f[j]=='
            c[i][j]+=1
            
yoko = [0]*h
tate = [0]*w
for i in range(h):
    yoko[i]=sum(c[i])
    for j in range(w):
        tate[j]+=c[i][j]
aaa = sum(yoko)
if aaa==k:
    ans=1
    for i in range(h):
        if yoko[i]==0:
            ans*=2
    for j in range(w):
        if tate[j]==0:
            ans*=2
    print(ans)
    exit()
    
ans = 0
for i in range(2**h-1):
    for j in range(2**w-1):
        cnt=0
        check1=[]
        check2=[]
        for n in range(h):
            if (i>>n)&1:
                cnt+=yoko[n]
                check1.append(n)
        for m in range(w):
            if (j>>m)&1:
                cnt+=tate[m]
                check2.append(m)
        for n in check1:
            for m in check2:
                if c[n][m]==1:
                    cnt-=1
        if aaa-cnt==k:
            ans+=1
        

print(ans)

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

cnt = 0
for i in range(2**N):
    ans = []
    for co in a:
        ans.append(copy.copy(co))
    for j in range(N):
        if((i >> j) & 1):
            for k in range(len(ans)):
                ans[k][j] = 'r'
    for l in range(2**H):
        ans2 = []
        for co2 in ans:
            ans2.append(copy.copy(co2))
        for n in range(H):
            if((l >> n) & 1):
                for m in range(len(ans[n])):
                    ans2[n][m] = 'r'
        temp = 0
        for o in range(len(ans2)):
            for p in range(len(ans2[o])):
                if(ans2[o][p] == '
                    temp += 1
        if(temp == K):
            cnt += 1
print(cnt)

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

canvas_as_int = [int(s.replace('.','0').replace('

column_masks = [[int(s) for s in f"{j:b}".zfill(H)] for j in range(2**H)]

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

res = 0
for i in range(2**W):
    row_masked_canvas = [popcount(n&i) for n in canvas_as_int]
    blacks = [sum(c * r for c,r in zip(column_mask,row_masked_canvas)) for column_mask in column_masks]
    res += blacks.count(K)

print(res)

Solution (Python):
import copy
H,W,K = list(map(int, input().split()))
C = list(list(input()) for _ in range(H))
ans = 0
for i in range(2 ** H):
  tmp = copy.deepcopy(C)
  for j in range(H):
    if ((i >> j) & 1):
      pass
    else:
      tmp[j] = list("." * W)
  for k in range(2 ** W):
    tmp2 = copy.deepcopy(tmp)
    for l in range(W):
      if ((k >> l) & 1):   
        pass   
      else:
        for h in range(H):
          tmp2[h][l] = "."
    result = 0
    for m in range(H):
      result += tmp2[m].count("
    if result == K:
      ans += 1
print(ans)

Solution (Python):
from itertools import product

H, W, K = map(int, input().split())
c = list()
for _ in range(H):
    c.append(input())

combiH = list(product([False, True], repeat=H))
combiW = list(product([False, True], repeat=W))

BLACK = ''.join(c).count('

result = 0
for redH in combiH:
    for redW in combiW:
        redRemovedInOneLine = ''
        for h in range(H):
            if redH[h]:
                continue
            for w in range(W):
                if redW[w]:
                    continue
                redRemovedInOneLine += c[h][w]
        
        if redRemovedInOneLine.count('
            result += 1


print(result)

Solution (Python):
import numpy as np
Z=[]
H,W,K=map(int,input().split())
for i in range(H):
    data=list(map(str,input().split()))
    date=list(data[0])
    Z.append(date)
S=0

for i in range(2**(H+W)) :
    A=np.array(Z)
    for j in range(H+W) :
        if i>>j & 1 :
            if j<=H-1 : 
                A[j,:]="?"
            else :
                A[:,j-H]="?"
    count=np.count_nonzero(A=="
    if count==K :
        S=S+1

print(S)

Solution (Python):

import itertools as it
import copy

def main():
    H, W, K = map(int, input().split())
    C = []
    for h in range(H):
        C.append(list(input()))
    
    ans = 0
    Hlist = []
    Wlist = []

    for i in range(H+1):
        Hlist += list(it.combinations([x for x in range(H)], i))

    for j in range(W+1):
        Wlist += list(it.combinations([y for y in range(W)], j))

    for hli, wli in it.product(Hlist, Wlist):
        Ccopy = copy.deepcopy(C)
        for h in hli:
            Ccopy[h] = [0]*W
        
        for l in range(len(Ccopy)):
            for w in wli:
                Ccopy[l][w] = 0
        
        num = 0
        for li in Ccopy:
            num+= li.count('

        if num == K:
            ans += 1
    
    print(ans)




if __name__ == '__main__':
    main()

Solution (Python):

"""AtCoder Beginner Contest 173: C - H and V
https://atcoder.jp/contests/abc173/tasks/abc173_c
"""

import copy


def count_black(cells):
    count = 0
    for col in cells:
        count += col.count('
    return count


def draw_red_and_count(cells, xs, ys):
    for x in xs:
        for col in cells:
            col[x] = '@'
    for y in ys:
        for i in range(len(cells[y])):
            cells[y][i] = '@'
    return count_black(cells)


def main():
    H, W, K = list(map(int, input().split()))
    cells = [[0 for j in range(W)] for i in range(H)]
    for x in range(H):
        Cs = list(input())
        for y in range(W):
            cells[x][y] = Cs[y]

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

    ans = 0
    for xs in Xs:
        for ys in Ys:
            black_count = draw_red_and_count(copy.deepcopy(cells), xs, ys)
            if black_count == K:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import copy

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

A = [0,1]
h1 = list(itertools.product(A, repeat=h))
w1 = list(itertools.product(A, repeat=w))

ans = 0

for i in h1:
    for j in w1:
        c1 = copy.deepcopy(c)
        for ii in range(h):
            if i[ii]:
                for jjj in range(w):
                    c1[ii][jjj] = '.'
        for jj in range(w):
            if j[jj]:
                for iii in range(h):
                    c1[iii][jj] = '.'

        tmp = 0
        for ii in range(h):
            for jj in range(w):
                if c1[ii][jj] == '
                    tmp += 1
        if tmp == k:
            ans += 1

print(ans)

Solution (Python):
import itertools
H,W,K=map(int,input().split())
a=[]
ans=0
c=0
for i in range(H):
  t=input()
  c+=t.count('
  a.append(list(t))
for i in range(H+1):
  for j in range(W+1):
    for h in itertools.combinations(list(range(H)),i):
      for w in itertools.combinations(list(range(W)),j):
        b=c
        for k in h:
          for m in range(W):
            if a[k][m]=='
              b-=1  
        for l in w:
          for n in range(H):
            if a[n][l]=='
              b-=1
        for k in h:
          for l in w:
            if a[k][l]=='
              b+=1
        if b==K:
          ans+=1
print(ans)

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

import itertools, copy


ans = 0

for h in range(H+1):
    for w in range(W+1):
        
        comb_h = list(itertools.combinations(list(range(H)), h))
        comb_w = list(itertools.combinations(list(range(W)), w))

        
        
        
        for ch in comb_h:
            for cw in comb_w:
                C_ = copy.deepcopy(C)
                
                for x in ch:
                    for i in range(W):
                        C_[x][i] = "R"
                for y in cw:
                    for i in range(H):
                        C_[i][y] = "R"
                        
                
                
                
                

                cnt = 0
                for x in range(H):
                    for y in range(W):
                        if C_[x][y] == "
                            cnt += 1
                            
                if cnt == K:
                    ans += 1
                    
                    

print(ans)

Solution (Python):
import numpy as np

H,W,K = map(int, input().split())
graph = np.array([[1 if x == "
count = 0
ans = 0
for i in range(2**H):
    mas = np.copy(graph)
    for h in range(H):
        if 1 & (i >> h) == 1:
            mas[h,:] = 0
    for j in range(2**W):
        mass = np.copy(mas)
        for w in range(W):
            if 1 & (j >> w):
                mass[:,w] = 0
        if mass.sum() == K:
            count += 1

print(count)

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, combinations_with_replacement

import copy
H, W, K = [int(_) for _ in input().split()]
C = [input() for i in range(H)]

def calc(lis):
    global C, K

    c = copy.copy(C)

    for i in lis:
        if i // 10 == 1:
            c[i%10-1] = "-" * W
        else:
            for j in range(H):
                tmp = list(c[j])
                tmp[i-1] = "-"
                c[j] = "".join(tmp)

    ct = 0
    for i in c:
        a = Counter(i)
        ct += a["
    
    if ct == K:
        return 1
    return 0
                
count = 0
lis = list(range(1, W + 1)) + list(range(11, 10 + H + 1))

ret = 0
for i in range(H+W):
    for com in list(combinations(lis, i)):
        ret += calc(com)

print(ret)

Solution (Python):
h,w,k=map(int,input().split())
import numpy as np
L=[]
for i in range(h):
    l=list(input())
    for j in range(w):
        if l[j]=='
            l[j]=1
        else:
            l[j]=0
    L.append(l)
r=np.asarray(L)
ans=np.sum(r)-k
p=np.sum(r,axis=1)
q=np.sum(r,axis=0)
pp=[]
qq=[]
import itertools as it
for i in range(1,h+1):
    for j in it.combinations([x for x in range(h)],i):
        pp.append(j)
for i in range(1,w+1):
    for j in it.combinations([x for x in range(w)],i):
        qq.append(j)
ok=0
for t in it.product(pp,qq):
    s=0
    for pairs in it.product(t[0],t[1]):
        s += r[pairs[0]][pairs[1]]
    P=0
    for i in t[0]:
        P += p[i]
    Q=0
    for i in t[1]:
        Q += q[i]
    if P+Q-s==ans:
        ok += 1
for i in pp:
    num=0
    for j in i:
        num += p[j]
    if num==ans:
        ok += 1
for i in qq:
    num=0
    for j in i:
        num += q[j]
    if num==ans:
        ok += 1
if ans==0:
    ok += 1
print(ok)

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


def count(a):
    re = 0
    for n in a:
        for m in n:
            if m == "
                re += 1
    return re


result = 0
for i in range(2**H):
    for j in range(2**W):
        temp_c = copy.deepcopy(c)
        sh = format(i, "0" + str(H) + "b")
        sw = format(j, "0" + str(W) + "b")
        for z, s in enumerate(sh):
            if s == "1":
                temp_c[z] = ["." for x in range(W)]

        for z, s in enumerate(sw):
            if s == "1":
                for y in range(len(temp_c)):
                    temp_c[y][z] = "."
        res = count(temp_c)
        if res == K:
            result += 1

print(result)

Solution (Python):
h, w, k = map(int, input().split())
cnt = 0
cntrem = 0
answer = 0
b = []
flag = [[0] * w for _ in range(h)]
for i in range(h):
    b.append(input())
    cnt += b[i].count('

copy = b
for i in range(2 ** h):
    cntrem = 0
    flag = [[0] * w for _ in range(h)]

    for j in range(h):
        if (i >> j) & 1:
            cntrem += b[j].count('

            for roop_w in range(w):
                flag[j][roop_w] = 1
    
    
    tmp = cntrem
    for ka in range(2 ** w):
        cntrem = tmp
        for l in range(w):
            if (ka >> l) & 1:
                for roop_h in range(h):
                    
                    
                    if flag[roop_h][l] == 0 and b[roop_h][l] == '
                        cntrem += 1

                

        
        if cnt - cntrem == k:
            answer += 1

print(answer)

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

Solution (Python):
import itertools
import copy
h,w,k=map(int,input().split())
c=[list(input()) for _ in range(h)] 
num=0
for i in range(h):
    for j in range(w):
        if c[i][j]=='
            num+=1
ans=0
for a in range(1,h+1):
    for b in range(1,w+1):
        l=range(1,h+1)
        m=range(1,w+1)
        for p in itertools.combinations(l, a):
            for q in itertools.combinations(m, b):
                sum=0
                d=copy.deepcopy(c)
                for i in p:
                    for j in q:
                        for s in range(w):
                            if d[i-1][s]=='
                                sum+=1
                                d[i-1][s]='.'
                        for t in range(h):
                            if d[t][j-1]=='
                                sum+=1
                                d[t][j-1]='.'
                if num-sum==k:
                    ans+=1
for a in range(1,h+1):
        l=range(1,h+1)
        for p in itertools.combinations(l, a):
            sum=0
            d=copy.deepcopy(c)
            for i in p:
                for s in range(w):
                    if d[i-1][s]=='
                        sum+=1
                        d[i-1][s]='.'
            if num-sum==k:
                ans+=1
for b in range(1,w+1):
        m=range(1,w+1)
        for q in itertools.combinations(m, b):
            sum=0
            d=copy.deepcopy(c)
            for j in q:
                for t in range(h):
                    if d[t][j-1]=='
                        sum+=1
                        d[t][j-1]='.'
            if num-sum==k:
                ans+=1
if num==k:
    ans+=1
print(ans)

Solution (Python):

"""AtCoder Beginner Contest 173: C - H and V
https://atcoder.jp/contests/abc173/tasks/abc173_c
"""

import copy


def debug_cells(cells):
    for col in cells:
        print(''.join(col))


def count_black(cells):
    count = 0
    for col in cells:
        count += col.count('
    return count


def draw_and_count(cells, xs, ys):
    for x in xs:
        for col in cells:
            col[x] = '@'
    for y in ys:
        for i in range(len(cells[y])):
            cells[y][i] = '@'
    
    return count_black(cells)


def main():
    H, W, K = list(map(int, input().split()))
    cells = [[0 for j in range(W)] for i in range(H)]
    for x in range(H):
        Cs = list(input())
        for y in range(W):
            cells[x][y] = Cs[y]

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

    
    
    ans = 0
    for xs in Xs:
        for ys in Ys:
            black_count = draw_and_count(copy.deepcopy(cells), xs, ys)
            if black_count == K:
                ans += 1
            
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
import copy

def main():
    h, w, k = map(int, input().split())
    c = [list(input()) for _ in range(h)]
    ans = solve(h, w, k, c)
    print(ans)

def solve(h, w, k, c):
    ans = 0
    for i in range(2 ** h):
        for j in range(2 ** w):
            cc = copy.deepcopy(c)
            for ii in range(h):
                if i >> ii & 1:
                    cc[ii] = ["!"] * w
            for jj in range(w):
                if j >> jj & 1:
                    for kk in range(h):
                        cc[kk][jj] = "!"
            tmp = [inner for outer in cc for inner in outer]
            if tmp.count('
                ans += 1
    return ans

if __name__ == '__main__':
    main()

Solution (Python):
H, W, K = map(int, input().split())
g = [input() for _ in range(H)]
ans = 0
for bit in range(2**(H + W)):
    cnt = 0
    for h in range(H):
        if (bit & (h << 1)):
            pass
        if ((bit >> h) & 1):
            
            continue
        for w in range(W):
            if (bit & (H + w << 1)):
                pass
            if ((bit >> H + w) & 1):
                continue
            if g[h][w] == '
                cnt += 1
                
    if cnt == K:
        
        
        
        ans += 1
print(ans)

Solution (Python):
h,w,K=map(int,input().split())
c=[list(input()) for _ in range(h)]
ans=0
for i in range(2**h):
  cc=[]
  for j in range(h): 
    if ((i >> j) & 1):
      continue
    else:
      cc.append(c[j])
  cc=[list(x) for x in zip(*cc)]
  for k in range(2**w):
    ccc=[]
    for l in range(w): 
      if ((k >> l) & 1):
        continue
      else:
        if not cc==[]:
          ccc.append(cc[l])
    cnt=0
    for v in ccc:
      cnt+=v.count('
    if cnt==K:
      ans+=1
print(ans)

Solution (Python):
from itertools import combinations
from copy import copy


def judge(color, rows, cols, H, W):
    h_ = list("_"*H)
    w_ = list("_"*W)
    for row in rows:
        color[row] = w_
    color = list(zip(*color))
    for col in cols:
        color[col] = h_
    color = sum(map(tuple, color), ())
    return color.count("


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

h_selector = []
w_selector = []
for i in range(H+1):
    h_selector.extend(list(combinations(range(H), i)))
for i in range(W+1):
    w_selector.extend(list(combinations(range(W), i)))

ans = 0
calc = 0
for rows in h_selector:
    for cols in w_selector:
        calc += 1
        t = copy(c)
        if judge(t, rows, cols, H, W) == K:
            ans += 1

print(ans)

Solution (Python):
h,w,k=map(int,input().split())
ori=[]
for i in range(h):
  a=str(input())
  
  ori.append(a)


t=[]
y=[]
for i in range(h):
  t.append(ori[i].count("

total=sum(t)

for j in range(w):
  now=0
  for i in range(h):
    noww=str(ori[i])
    
    if noww[j]=="
      now+=1
  y.append(now)

  


import itertools

ans=0
check=0
listate = [i for i in range(h)]
lisyoko = [i for i in range(w)]
for n in range(1,len(listate)+1):
    for tat in itertools.combinations(listate, n):
      tate=list(tat)
      for n in range(1,len(lisyoko)+1):
        for yok in itertools.combinations(lisyoko, n):
          yoko=list(yok)

          now=total
          
          for j in yok:
            now-=y[j]
          for i in tate:
            now-=t[i]
            noww=str(ori[i])
            for j in yok:
              if noww[j]=="
                now+=1
          check+=1
          if now==k:
            ans+=1
            
            
for n in range(1,len(listate)+1):
    for tat in itertools.combinations(listate, n):
      tate=list(tat)
      now=total
      for i in tate:
        now-=t[i]
      check+=1
      if now==k:
        ans+=1
        

for n in range(1,len(lisyoko)+1):
  for yok in itertools.combinations(lisyoko, n):
    yoko=list(yok)
    now=total
    for i in yoko:
      now-=y[i]
    check+=1
    if now==k:
      ans+=1
      
if total==k:
  ans+=1
print(ans)