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
import copy
H, W, K = map(int, input().split())
C = []
for _ in range(H):
    C.append([c for c in input()])

H_list = [i for i in range(H)]
H_comb = []
for i in range(1, H):
    H_comb += itertools.combinations(H_list, i)

W_list = [i for i in range(W)]
W_comb = []
for i in range(1, W):
    W_comb += itertools.combinations(W_list, i)

ans = 0
cnt = 0
for w in C: cnt += w.count('
if cnt == K: ans += 1

for wc in W_comb:
    temp_C0 = copy.deepcopy(C)
    for i in sorted(wc, reverse=True):
        for w in temp_C0: w.pop(i)
    cnt = 0
    for w in temp_C0 : cnt += w.count('
    if cnt == K: ans += 1

for hc in H_comb:
    temp_C1 = copy.deepcopy(C)
    for i in sorted(hc, reverse=True): temp_C1.pop(i)
    cnt = 0
    for w in temp_C1: cnt += w.count('
    if cnt == K: ans += 1
    for wc in W_comb:
        temp_C2 = copy.deepcopy(temp_C1)
        for j in sorted(wc, reverse=True):
            for w in temp_C2: w.pop(j)
        cnt = 0
        for w in temp_C2 : cnt += w.count('
        if cnt == K: ans += 1
print(ans)

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

C = []

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

ans = 0
for i in reversed(range(2 ** (h + w))):
    d = copy.deepcopy(C)
    x = []
    for j in reversed(range(h + w)):
        if ((i >> j) & 1):
            x.append(j)
            if j < h:
                del d[j]
            if h <= j:
                m = j - h
                for k in range(len(d)):
                    del d[k][m]
    
    count = 0
    for n in d:
        count += n.count('
    if count == K:
        ans += 1
print(ans)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	
	h, w, k = tin()
	bl = [[1 if c == '
	
	cc = 0
	for hhi in range(2**h - 
	1):
		for wwi in range(2**w -	1):
			n = 0
			for hi, l in enumerate(bl):
				if hhi & (2**hi) > 0:
					continue
				for wi, v in enumerate(l):
					if wwi & (2**wi) > 0:
						continue
					n += v
			if n == k:
				
				cc += 1
			
	return cc
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):


import itertools
import copy

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

ccs = []

hnum = list(range(h))
wnum = list(range(w))

def countBlack(cc):
    ans = 0
    for i in range(h):
        ans += cc[i].count('
    return ans

ans = 0

for i in range(w+1):
    for comb_column in list(itertools.combinations(wnum, i)):
        for p in range(h+1):
            for comb_row in list(itertools.combinations(hnum, p)):

                if len(comb_column)==w or len(comb_row)==h:
                    break

                cc = copy.deepcopy(c) 
                
                
                
                
                
                for j in range(len(comb_column)):
                    for j2 in range(h):
                        cc[j2][comb_column[j]] = 'R'

                
                for q in range(len(comb_row)):
                    for r in range(w):
                        cc[comb_row[q]][r] = 'R'

                
                
                
                

                ccs.append(cc)

for i in ccs:
    if k == countBlack(i):
        ans += 1

print(ans)

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

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

ans = 0
for hl in product([0, 1], repeat=h):
    for wl in product([0, 1], repeat=w):
        cc = deepcopy(c)
        for i, hi in enumerate(hl):
            for j, wj in enumerate(wl):
                if hi == 1 or wj == 1:
                    cc[i][j] = 'r'
        cnt = 0
        for s in cc:
            cnt += sum(si == '
        if cnt == k:
            ans += 1
print(ans)

Solution (Python):
import numpy as np


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

c = np.empty(0)

for i in range(H):
    tmp = list(input())
    c = np.append(c, tmp)
    
c = c.reshape([H, W])

num = 0
_max = 2 ** (H+W)
count = 0

for i in range(_max):
    bin_num = format(num, 'b')
    for j in range((H+W) - len(bin_num)):
        bin_num = '0' + bin_num
    tmp = bin_num
    c2 = c.copy()
    for j in range(H):
        if bin_num[j] == '1':
            c2[j, :] = 'r'
    for j in range(H, H+W):
        if bin_num[j] == '1':
            c2[:, j-H] = 'r'
    if np.count_nonzero(c2 == '
        count += 1
    num += 1
        
print(count)

Solution (Python):
import itertools

h,w,k=[int(x) for x in input().rstrip().split()]
l=[]
bl=0
yoko=[]
tate=[]
ans=0
for i in range(h):
  W=[x for x in input()]
  l.append(W)
  bl=0
  for s in W:
    if s=="
      bl+=1
  yoko.append(bl)

for i in range(w):
  bl=0
  for j in range(h):
    if l[j][i]=="
      bl+=1
  tate.append(bl)

ans=0
if sum(tate)==k:
  ans=1
else:
  ans=0
Y=[]
y_l=[i for i in range(len(yoko))]
for i in range(1,len(yoko)+1):
  for ii in itertools.combinations(y_l,i):
    a=0
    for s in ii:
      a+=yoko[s]

    if sum(tate)-a==k:
      ans+=1
    Y.append(ii)
t_l=[i for i in range(len(tate))]
X=[]
for i in range(1,len(tate)+1):
  for ii in itertools.combinations(t_l,i):
    a=0
    for s in ii:
      a+=tate[s]
    if sum(tate)-a==k:
      ans+=1
    X.append(ii)

now=0
for i in X:
  for j in Y:
    for ii in i:
      now+=tate[ii]
    for jj in j:
      now+=yoko[jj]
    for jj in j:
      for ii in i:
        if l[jj][ii]=="
          now-=1
    if sum(tate)-now==k:
      ans+=1
    now=0
print(ans)

Solution (Python):
import itertools

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

kuro = []

for i in range(h):
    tmp = input()
    a = []
    for j in tmp:
        if j == '
            a.append(True)
        else:
            a.append(False)
        
    kuro.append(a)

ans=0
for i in range(h+1):
  for j in range(w+1):
    for n in itertools.combinations(list(range(h)),i):
      for m in itertools.combinations(list(range(w)),j):
        count = 0
        for a in n:
          for b in m:
            if(kuro[a][b]):count+=1
        if(count == k):
          ans += 1
print(ans)

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

c = []
count = 0
for i in range(h):
    cl = list(input())
    c.append(cl)
    count += cl.count("

hc = 2 ** h
wc = 2 ** w
result = 0

for i in range(hc):
    for j in range(wc):
        mc = 0
        hc2 = i
        hclis = []
        if i == 0:
            hclis = [0]
        while hc2 != 0:
            hclis.append(hc2 % 2)
            hc2 = hc2 // 2
        wc2 = j
        wclis = []
        if j == 0:
            wclis = [0]
        while wc2 != 0:
            wclis.append(wc2 % 2)
            wc2 = wc2 // 2
        for k1 in range(len(hclis)):
            if hclis[k1] == 1:
                mc += c[k1].count("
        for k2 in range(len(wclis)):
            if wclis[k2] == 1:
                for l in range(h):
                    if c[l][k2] == "
                        mc += 1
        for k1 in range(len(hclis)):
            for k2 in range(len(wclis)):
                if hclis[k1] == 1 and wclis[k2] == 1 and c[k1][k2] == "
                    mc -= 1

        if count - mc == k:
            result += 1

print(result)

Solution (Python):
import sys
import numpy as np
import itertools
input = lambda: sys.stdin.readline().rstrip()

def main():
    h, w, k = map(int, input().split())
    ans = 0
    grid = []
    index = [i for i in range(h + w)]
    for _ in range(h):
        grid.append(list(input()))
    grid = np.array(grid)
    if np.count_nonzero(grid == '
        ans += 1
    for i in range(1, h+w+1):
        for combs in itertools.combinations(index, i):
            tmp = grid.copy()
            row, col = [], []
            for comb in combs:
                if comb >= w:
                    row.append(comb - w)
                else:
                    col.append(comb)
            tmp = np.delete(tmp, row, 0)
            tmp = np.delete(tmp, col, 1)
            if np.count_nonzero(tmp == '
                ans += 1
    print(ans)                
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    ans = 0
    H,W,K = map(int, input().split())
    l = []
    for _ in range(H):
        l.append(list(input().rstrip('\n')))
    for i in range(2**H):
        for j in range(2**W):
            b = 0
            for h in range(H):
                for w in range(W):
                    if i>>h & 1 and j>>w & 1 and l[h][w] == '
                        b += 1
            if b == K:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):



import numpy as np
import itertools
import copy


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


white = '.'
black = '

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

for i in range(h):
    for j in range(w):
        c2[i][j] = 1 if c[i][j] == black else 0


pattern = []
cnt = 0
for _h in list(itertools.product([0, 1], repeat=h)):
    for _w in list(itertools.product([0, 1], repeat=w)):
        pattern.append((_h, _w))

cnt = 0
for p in pattern:
    
    test_c = copy.deepcopy(c2)
    for i, ih in enumerate(p[0]):
        for j, jw in enumerate(p[1]):
            if ih == 0 or jw == 0:
                test_c[i][j] = 0
    sum = np.array(test_c).sum()
    

    if sum == k:
        cnt += 1

print(cnt)

Solution (Python):
import sys, copy
input = sys.stdin.readline
def main():
    h, w , k = map(int, input().split())
    ls = []
    for _ in range(h):
        ms = []
        t=str(input().rstrip())
        for i in range(len(t)):
            if t[i] =='.':
                ms.append(0)
            else:
                ms.append(1)
        ls.append(ms)

    def num(x, y):
        lt = copy.deepcopy(ls)
        x2 = format(x, 'b').rjust(h, '0')
        y2 = format(y, 'b').rjust(w, '0')
        for i in range(len(x2)):
            if x2[i]=='0':
                lt[i]= [0]*len(y2)
        for j in range(len(y2)):
            if y2[j]=='0':
                for t in range(len(x2)):
                    lt[t][j]= 0
        re = 0
        for i in lt:
            re += sum(i)

        return re

    ans = 0
    for i in range(2**h):
        for j in range(2**w):
            if num(i,j) == k:
                ans +=1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
h, w, k=map(int,input().split())
masu =[input() for _ in range(h)]
ans=0
for x in range(2**h):
    for y in range(2**w):
        cnt=0
        for i in range(h):
            for j in range(w):
                if x>>i&1 and y>>j&1 and masu[i][j]=="
                    cnt+=1
        if cnt == k:
            ans += 1
print(ans)

Solution (Python):
import numpy as np

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

c = [[1 if s=="

def func(mats, ans, h, hmax, w, wmax):
  buf = []
  if h<hmax:
    for mat in mats:
      m = mat.copy()
      m[h,:] = 0
      s = m.sum()
      if s>K:
        buf.append(m)
      if s==K:
        ans.append(m)
        buf.append(m)
      buf.append(mat)
    func(buf, ans, h+1, hmax, w, wmax)
  elif w < wmax:
    for mat in mats:
      m = mat.copy()
      m[:,w] = 0
      s = m.sum()
      if s>K:
        buf.append(m)
      if s==K:
        ans.append(m)
        buf.append(m)
      buf.append(mat)
    func(buf, ans, h, hmax, w+1, wmax)
  else:
    return

ans = []
if np.array(c).sum()==K:
  ans.append(np.array(c))
func([np.array(c)], ans, 0, H, 0, W)
print(len(ans))

Solution (Python):



import numpy as np
import itertools


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


white = '.'
black = '

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

for i in range(h):
    for j in range(w):
        c2[i][j] = 1 if c[i][j] == black else 0

nc = np.array(c2)

black_total = np.sum(c2)

h_blacks = list(np.sum(c2, axis=1))
w_blacks = list(np.sum(c2, axis=0))




import copy


pattern = []
cnt = 0
for _h in list(itertools.product([0, 1], repeat=h)):
    for _w in list(itertools.product([0, 1], repeat=w)):
        pattern.append((_h, _w))

cnt = 0
for p in pattern:
    
    test_c = copy.deepcopy(c2)
    for i, ih in enumerate(p[0]):
        for j, jw in enumerate(p[1]):
            if ih == 0 or jw == 0:
                test_c[i][j] = 0
    sum = np.array(test_c).sum()
    

    if sum == k:
        cnt += 1

print(cnt)

Solution (Python):
H,W,K=map(int,input().split())
c=[list(input()) for i in range(H)]
count=0
for bit_h in range(1<<H):
    for bit_w in range(1<<W):
        black=0
        for h in range(H):
            for w in range(W):
                if c[h][w]=="
                    black+=1
        if black==K:
            count+=1
print(count)

Solution (Python):
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前
sort()
sorted(reverse=true)
配列の初期化
配列名=[a]*n+[b]*m
Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys
d = stdin.readline().rstrip().split()
H = int(d[0])
W = int(d[1])
K = int(d[2])

data = []
bCount = 0
result = 0
for el1 in range(H):
    tmp = stdin.readline().rstrip().split()
    d = []
    for el in tmp:
        for el3 in el:
            if el3 == '
                bCount += 1
            d.append(el3)
    data.append(d)
datas = copy.deepcopy(data)
counter = 0
for el in range(H+W):
    counter += 2**el
for el in range(counter+1):
    bin_str = ''.join(list(reversed(str(bin(el))[2:])))
    poss = []
    count = 0
    for el2 in bin_str:
        if el2 == '1':
            poss.append(count)
        count += 1
    res = 0
    for el2 in poss:
        if el2 >= H:
            el2 -= H
            for el3 in datas:
                el3[el2] = 'o'
        else:
            datas[el2] = ['o']*W
    for el2 in datas:
        res += el2.count('
    if res == K:
        result += 1
    datas = copy.deepcopy(data)
print(result)

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

masu = []
for h in range(H):
    tmp = [1 if i == "
    masu.append(tmp)

ans = 0

h_product = list(itertools.product([0, 1], repeat=H))
w_product = list(itertools.product([0, 1], repeat=W))

for h_pro in h_product:
    for w_pro in w_product:
        tmp = 0
        for h in range(len(h_pro)):
            for w in range(len(w_pro)):
                tmp += h_pro[h] * w_pro[w] * masu[h][w]
        if tmp == K:
            ans += 1
                
       
print(ans)

Solution (Python):
h,w,k=map(int,input().split())
C=[list(input().strip()) for _ in range(h)]
ans=0
for i in range(1<<h):
    for j in range(1<<w):
        cnt=0
        for x in range(h):
            if (i>>x)&1==1:
                continue
            for y in range(w):
                if (j>>y)&1==1:
                    continue
                cnt+=int(C[x][y]=='
        if cnt==k:
            ans+=1
print(ans)

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

ret = 0

for i in range(1 << h):
    for j in range(1 << w):
        cnt = 0
        for x in range(h):
            for y in range(w):
                if c[x][y] == '
                    cnt += 1
        if cnt == k:
            ret += 1

print(ret)

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

grid = []
ans = 0
for _ in range(H):
    grid.append(list(input()))

for i in range(2**H):
    for j in range(2**W):
        now = 0
        for x in range(H):
            for y in range(W):
                if 2 ** x & i > 0  and 2**y & j > 0:
                    if grid[x][y] == "
                        now += 1
        if now == K:
            ans += 1
print(ans)

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

c = []
nb = 0
for _ in range(h):
   tmp = [x for x in input()]
   nb += tmp.count('
   c.append(tmp)

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

x = [0] * h
for i in range(h):
   x[i] = c[i].count('

ans = 0
for i in range(2**h):
   y = [0] * w
   for j in range(w):
      y[j] = d[j].count('

   cnt1 = 0
   for ik in range(h):
      if ((i >> ik) & 1):
         cnt1 += x[ik]
         for j in range(w):
            if c[ik][j] == '
               y[j] -= 1

   for j in range(2**w):
      cnt2 = 0
      for jk in range(w):
         if ((j >> jk) & 1):
            cnt2 += y[jk]

      if(nb - (cnt1 + cnt2)) == k:
         ans += 1

print(ans)

Solution (Python):
h, w, k=map(int,input().split())
masu =[input() for _ in range(h)]
ans=0
for x in range(2**h):
    for y in range(2**w):
        cnt=0
        for i in range(h):
            for j in range(w):
                if x>>i&1 and y>>j&1 and masu[i][j]=="
                    cnt+=1
        if cnt == k:
            ans += 1
print(ans)

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

MasuMoji=[input() for i in range(H)]  


def countAllmasu(masu,H,W):
  total=0
  for h in range(H):
    for w in range(W):
      total+=masu[h][w]
  return(total)


masu=[]
for h in range(H):
  masu.append([])
  for w in range(W):
    if MasuMoji[h][w]==".":
    	masu[h].append(0)
    else:
        masu[h].append(1)
  

H_OI=[]
for i in range(2 ** H):
    OI=[]
    
    for j in range(H):  
        if ((i >> j) & 1):  
            OI.append(1)  
        else:
            OI.append(0)
            
    H_OI.append(OI)

  
W_OI=[]
for i in range(2 ** W):
    OI=[]
    
    for j in range(W):  
        if ((i >> j) & 1):  
            OI.append(1)  
        else:
            OI.append(0)
            
    W_OI.append(OI)

patterns=0


for h in H_OI:
  for w in W_OI:
      
    tempmasu= copy.deepcopy(masu)

    for h2 in range(H):
      for w2 in range(W):
        if h[h2]==1 or w[w2]==1:
          tempmasu[h2][w2]=0


    
    if countAllmasu(tempmasu,H,W)==K:
      patterns+=1
      
print(patterns)

Solution (Python):
from itertools import combinations
from copy import deepcopy
numCount = 0
h, w, k = map(int, input().split())
cList = []
for i in range(h):
    toAdd = list(input())
    cList.append(toAdd)
for i in range(h + 1):
    hCom = list(combinations(list(range(h)), i))
    hComKai = []
    for l in hCom:
        hComKai.append(list(l))
    for j in range(w + 1):
        for u in hComKai:  
            cListKai = deepcopy(cList)
            for o in sorted(u, reverse=True):
                cListKai.pop(o)
            kCom = list(combinations(list(range(w)), j))
            kComKai = []
            for p in kCom:
                kComKai.append(list(p))
            for y in kComKai:
                cListKaiKai = deepcopy(cListKai)
                for t in sorted(y, reverse=True):
                    for r in cListKaiKai:
                        r[t] = '.'
                bkCount = 0
                for q in cListKaiKai:
                    for a in q:
                        if a == '
                            bkCount += 1
                if bkCount == k:
                    numCount += 1

print(numCount)

Solution (Python):
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy

H, W, K = map(int, input().split())
dump(H, W, K)
c = []
for i in range(H):
    c.append(input())
dump(c)
ans = 0
for rows, columns in it.product(it.product({True, False}, repeat=H), it.product({True, False}, repeat=W)):
    rIdx = {i for i, ri in enumerate(rows) if ri}
    cIdx = {j for j, cj in enumerate(columns) if cj}
    dump(rIdx, cIdx)
    cnt = 0
    for i in range(H):
        for j in range(W):
            if (i not in rIdx) and (j not in cIdx) and (c[i][j] == '
                cnt += 1
    dump(cnt)
    if cnt == K:
        ans += 1
print(ans)

Solution (Python):
import numpy as np 
h,w,k=map(int,input().split())
c=[None]*h
for i in range(h):
  c[i]=list(map(int,input().replace(".","0 ").replace("

d=np.array(c)
c=np.copy(d)
e=np.copy(c)
r=0


for j in range(2**h):
  j_b=bin(j)[:1:-1]
  e=np.copy(c)
  
  for i_j,d_j in enumerate(j_b):
    
    if d_j=="1":
      
      e[i_j]=0
      
    
    
  for m in range(2**w):
    d=np.copy(e)
      
    m_b=bin(m)[:1:-1]
      
      
    for i_m,d_m in enumerate(m_b):
      if d_m=="1":
        d[:,i_m]=0
        
          
        
      
    if np.sum(d)==k:
      r+=1
        
        
        
      
    
print(r)

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

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

C = []
base = 0
for i in range(H):
	string = input()
	string = string.replace('.', '0')
	string = string.replace('
	lst = list(string)
	lst = [int(c) for c in lst]
	C.append(lst)
	base += sum(lst)

C = np.array(C)
orig = C.copy()
count = 0

for i in range(H+1):
	for j in range(W+1):
		for c in combinations(range(H), i):
			for d in combinations(range(W), j):
				for row in c:
					C[row] = [0] * W
				for col in d:
					C[:, col] = [0] * H
				if np.sum(C) == K:
					count += 1
				C = orig.copy()

print(count)

Solution (Python):
import itertools
import copy

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

p_list = list(itertools.product(range(0, 2), repeat = (h + w)))

for i in range(len(p_list)):
    damy = copy.deepcopy(c_list)
    for j in range(h):
        if p_list[i][j] == 1:
            damy[j] = ["."] * w
    for j in range(w):
        if p_list[i][h + j] == 1:
            for l in range(h):
                damy[l][j] = "."
    count = 0
    for j in range(h):
        count += damy[j].count('
    if count == k:
        ans += 1

print(ans)

Solution (Python):
import itertools
import copy
H,W,K= map(int,input().split())
List=[list(input()) for i in range(H)]
nums=[]
total=0
for i in range(1,H+W+1):
    nums.append(i)
for q in range(0,H+W+1):
    hoge=[]
    for balls in itertools.combinations(nums, q):
        hoge.append(balls)
    for p in range(0,len(hoge)):
        Listo=copy.deepcopy(List)
        for i in range(1,H+1):
            if i in hoge[p]:
                for j in range(0,W):
                    Listo[i-1][j]="x"
        for i in range(H+1,H+W+1):
            if i in hoge[p]:
                for j in range(0,H):
                    Listo[j][i-H-1]="x"
        s=0
        for i in range(0,H):
            for j in range(0,W):
                if Listo[i][j]=="
                    s+=1
        if s== K:
            total+=1
print(total)

Solution (Python):
import numpy as np
import sys

def combinationlist(n):
    p_sets = []
    for i in range(2 ** n):
        lst = [x + 1 for x in range(i) if 2 **x & i]
        if lst != []:
            p_sets.append(lst)
    p_sets = sorted(p_sets, key=lambda x: len(x))
    return p_sets


def main():
    data = input().split()
    h = int(data[0])
    w = int(data[1])
    k = int(data[2])
    c = np.empty((h,w),dtype=str)
    for i in range(h):
        s = input()
        c[i,:] = np.array([c for c in s])
    rowset = []
    colset = []
    all_black = 0
    for i in range(h):
        data = c[i,:]
        count = len(data[data == '
        all_black += count
        rowset.append([count, data])
    for j in range(w):
        data = c[:,j]
        count = len(data[data=='
        colset.append([count,data])
    ans = 0
    if k == all_black:
        ans += 1
    rowList = combinationlist(h)
    colList = combinationlist(w)
    for comb in rowList:
        if w*len(comb) > h*w - k:
            continue
        count = 0
        for i in  comb:
            count += rowset[i-1][0]
        if count == all_black - k:
            ans += 1
        if count <= all_black - k:
            for comb_2 in colList:
                comb_count = count
                for j in comb_2:
                    comb_count += colset[j-1][0]
                    for s in comb:
                        if '
                            comb_count = comb_count -1
                if comb_count == all_black - k:
                    ans += 1
    for comb in colList:
        if h*len(comb) > h*w - k:
            continue
        count = 0
        for i in  comb:
            count += colset[i-1][0]
        if count == all_black - k:
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
h, w, k = map(int, input().split())
_map = np.zeros((h, w), dtype = int)
ans = 0
for i in range(h):
  _str = list(input())
  for j in range(w):
    if (_str[j] == "
      _map[i, j] = 1
      
for i in range(2**(h + w)):
  _array = np.copy(_map)
  for j in range(h + w):
    if ((i >> j) & 1):
      if j < h:
        _array[j, :] = 0
      else:
        _array[:, j - h] = 0
  if np.sum(_array) == k:
    ans += 1
print(ans)

Solution (Python):
import itertools
h,w,k = map(int,input().split())
c = []
row = list(itertools.product(range(2),repeat=h))
col = list(itertools.product(range(2),repeat=w))
for i in range(h):
    c.append(input())

ans = 0

for arr_row in row:
    for arr_col in col:
        val = 0
        for i in range(h):
            for j in range(w):
                if c[i][j] == "
                    val +=1
        if val == k:
            ans +=1
print(ans)

Solution (Python):
import itertools

h, w, k = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for x, y in itertools.product(range(2 ** h), range(2 ** w)):
    cnt = 0
    for i, j in itertools.product(range(h), range(w)):
        if x >> i & 1 or y >> j & 1: continue
        if c[i][j] == '
    if cnt == k:
        ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


def read_map_as(H, replace={'
    '''
    文字列のmapを置換して読み込み。デフォでは
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            
            
    else:  
        ret = [[pad] * (W + 2)]  
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce
from math import gcd


def lcm(a, b):
    
    g = gcd(a, b)
    return a // g * b


H, W, K = ints()

import numpy as np
C = np.array(read_map_as(H))
ans = 0
for rows in product(range(2), repeat=H):
    C_r = C.copy()
    for i, tf in enu(rows):
        if tf:
            C_r[i, :] = 0
    for cols in product(range(2), repeat=W):
        C_rc = C_r.copy()
        for j, tf in enu(cols):
            if tf:
                C_rc[:, j] = 0
        ans += (C_rc.sum() == K)
print(ans)

Solution (Python):
h,w,k=map(int,input().split())
c=["" for i in range(h)]
checkw="."*w
gyou=[]
retu=[]
black=[]
alww=[]
alwh=[]
pat1=[]
pat2=[]
ans=0
for i in range(h):
    c[i]=input()
    for j in range(w):
        if (c[i][j]=="
            black.append(len(black))
            gyou.append(i)
            retu.append(j)
            

for i in range(2**h):
    tmp1 = [False] * (h)
    for j in range(h):
        if i >> j & 1:
            tmp1[j] = True
    pat2.append(tmp1)
    
for i in range(2**w):
    tmp2 = [False] * (w)
    for j in range(w):
        if i >> j & 1:
            tmp2[j] = True
    pat1.append(tmp2)


for i in range(len(pat1)):
    for j in range(len(pat2)):
        g=[]
        for x in range(w):
            if (pat1[i][x]==True):
                for l in range(len(black)):
                    if (retu[l]==x):
                        g.append(l)
        for y in range(h):
            if (pat2[j][y]==True):
                for l in range(len(black)):
                    if (gyou[l]==y):
                        g.append(l)
        
        
        
        
        
        
        
        if (k==len(black)-len(set(g))):
            
            
            ans+=1
            
print(ans)