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 copy

def count_num_of_black(c):
    num = 0
    for row in c:
        for e in row:
            if e == '
                num += 1
    return num


if __name__ == "__main__":
    H, W, K = list(map(int, input().split()))
    original = []
    ans = 0
    for i in range(H):
        original.append(list(input()))
    for l in range(2 ** H):
        c = copy.deepcopy(original)
        for i in range(H):
            if ((l >> i) & 1):
                c[i] = list('*'*W)            
            c_after_line_change = copy.deepcopy(c)
        for r in range(2 ** W):
            c_before_row_change = copy.deepcopy(c_after_line_change)
            for j in range(W):
                if ((r >> j) & 1):
                    for k in range(H):
                        c_before_row_change[k][j] = '*'
            if K == count_num_of_black(c_before_row_change):
                ans += 1

    print(ans)

Solution (Python):
import numpy as np

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

board = np.zeros((H, W), dtype=int)

for row in range(H):
    C = list(input())
    for col in range(W):
            board[row][col] = int(C[col] == "

ans = 0
for h in range(2 ** H):
    h_idx = list(map(int, list(map(int, str(bin(h))[2:].zfill(H)))))
    h_idx = [i for i, flag in enumerate(h_idx) if flag]
    for w in range(2 ** W):
        w_idx = list(map(int, list(map(int, str(bin(w))[2:].zfill((W))))))
        w_idx = [i for i, flag in enumerate(w_idx) if flag]
        if np.sum(board[h_idx][:, w_idx]) == K:
            ans += 1
print(ans)

Solution (Python):
import itertools
H, W, K = map(int, input().split())
table = [0 for i in range(H)]
ans = 0
S = 0

for i in range(H):
    table[i] = input()

for i in range(H+1):
    list_H = list(itertools.combinations(range(H), i))
    for X in list_H:
        for j in range(W+1):
            list_W = list(itertools.combinations(range(W), j))
            for Y in list_W:
                H_check = [0 for i in range(H)]
                W_check = [0 for i in range(W)]
                black = 0
                if i != 0:
                    for A in range(i):
                        H_check[X[A]] = 1
                if j != 0:
                    for B in range(j):
                        W_check[Y[B]] = 1
                for k in range(H):
                    for l in range(W):
                        if H_check[k] == 0 and W_check[l] == 0:
                            if table[k][l] == "
                                black += 1
                if black == K:
                    ans += 1
                
                
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
colors = []
for _ in range(H):
    colors.append(list(input()))
black_cnt = 0
for i in range(H):
    for j in range(W):
        if colors[i][j] == '
            black_cnt += 1

ans = 0
for i in range(2 ** H):
    
    tmp_black_cnt = black_cnt
    for j in range(H):
        if (i >> j) & 1:
            for k in range(W):
                if colors[j][k] == '
                    tmp_black_cnt -= 1
    
    for l in range(2 ** W):
        row_tmp_black_cnt = tmp_black_cnt
        for m in range(W):
            if l == 4:
                a = 1
            if (l >> m) & 1:
                for n in range(H):
                    if colors[n][m] == '
                        row_tmp_black_cnt -= 1
        for j in range(H):
            for m in range(W):
                if (l >> m) & 1 and (i >> j) & 1 and colors[j][m] == '
                    row_tmp_black_cnt += 1
        
        if row_tmp_black_cnt == K:
            ans += 1
print(ans)

Solution (Python):
H,W,K=map(int,input().split())
m=[]
for _ in range(H):
    m.append([1 if s=='


def cnt(m_in):
    ans = 0
    for r in m_in:
        ans +=sum(r)
    return ans

def paintred(lr,lc):
    
    '''
    m_ans = m
    for i in range(H):
        if lr[i] == 1:
            m_ans[i]=[0]*W
    for i in range(W):
        if lc[i] == 1:
            for j in range(H):
                m_ans[j][i]=0
    '''
    m_ans = [[0]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if lr[i]==0 and lc[j]==0 and m[i][j]==1:
                m_ans[i][j]=1
    return m_ans
        

def f(l):
    
    if len(l) == (H+W):
        lr=l[:H]
        lc=l[H:]
        m_tmp=paintred(lr,lc)
        
        if cnt(m_tmp) == K:
            
            return 1
        else:
            
            return 0
    ans = 0
    for binary in [0,1]:
        ans += f(l+[binary])
        
    return ans

print(f([]))

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

import numpy as np
import copy
import itertools


M = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if c[i][j]=='.':
            M[i][j] = 0
        else:
            M[i][j] = 1

l = [0,1]

h_list = list(itertools.product(l, repeat=H))
w_list = list(itertools.product(l, repeat=W))
h_list = np.array(h_list)
w_list = np.array(w_list)

ans = 0

for item_h in h_list:
    for item_w in w_list:
        tmp = copy.deepcopy(M)
        l = np.where(item_h==1)
        for item in l:
            tmp[item,:] = 0
        l = np.where(item_w==1)
        for item in l:
            tmp[:,item] = 0
        if np.sum(tmp) == K:
            ans += 1
 
print(ans)

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

import copy
ans = 0
for i in range(2**H):
    for j in range(2**W):
        tmp = copy.deepcopy(C)
        for k in range(H):
            if i>>k&1:
                for m in range(W):
                    tmp[k][m] = "r"
        for l in range(W):
            if j>>l&1:
                for n in range(H):
                    tmp[n][l] = "r"
        cnt = 0
        for a in range(H):
            for b in range(W):
                if tmp[a][b] == "
                    cnt += 1
        
        if cnt ==K:
            ans += 1

print(ans)

Solution (Python):
from collections import Counter

def solve(R, C, K, A):
  ans = 0
  for mask in range(1 << C):
    rsums = []
    for row in A:
      rsums.append(0)
      for c in range(C):
        if row[c] == '
          rsums[-1] += 1
      
    count = {0: 1}
    for s in rsums:
      count2 = Counter()
      for k in count:
        v = count[k]
        count2[k] += v
        count2[k + s] += v
      count = count2
    ans += count[K]
  return ans


R, C, K = map(int, raw_input().split())
A = [raw_input() for _ in xrange(R)]
print solve(R, C, K, A)

Solution (Python):
y,x,moku=map(int,input().split())
yoko=[0]*y 
tate=[0]*x 
glid=[0]*y
ans=0
for i in range(y):
  glid[i]=input()
  yoko[i]=glid[i].count('
m=sum(yoko)
for i in range(x):
  tmp=0
  for j in range(y):
    if glid[j][i]=="
      tmp+=1
  tate[i]=tmp
for i in range(2**x):
  xls=[]
  decx=0
  for k in range(x):
    if (i>>k)&1:
      xls.append(k)
      decx+=tate[k]
  for j in range(2**y):
    decy=0
    yls=[]
    for k in range(y):
      if (j>>k)&1:
        yls.append(k)
        decy+=yoko[k]
    decd=0
    for z in xls:
      for w in yls:
        if glid[w][z]=="
          decd+=1
    
    tmp=m-decx-decy+decd
    if tmp==moku:
      ans+=1
print(ans)

Solution (Python):
import copy


def get_int():
    return int(input())


def get_string():
    return input()


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


def get_string_list():
    return input().split()


def get_int_multi():  
    return map(int, input().split())


def get_string_char_list():
    return list(str(input()))





'''
while (idx < n) and ():

    idx += 1
'''

ans = 0

def recu(ori, ban, idx, h, w, k, ans):
    if idx == h + w:
        count = 0
        for m in range(h):
            for n in range(w):
                if ban[m][n] == "
                    count += 1
        if count == k:
            ans += 1
        return ans

    ans = recu(ori, ban, idx+1, h, w, k, ans)

    ban2 = copy.deepcopy(ban)

    if (idx < h):
        ban2[idx] = ["r"] * w
    else:
        for row in range(h):
            ban2[row][idx-h] = "r"

    ans = recu(ori, ban2, idx+1, h, w, k, ans)

    return ans

def main():
    h, w, k = get_int_multi()

    ans = 0
    ori_ban = []
    for num in range(h):
        ori_ban.append(get_string_char_list())

    print(recu(ori_ban, ori_ban, 0, h, w, k, 0))

if __name__ == '__main__':
    main()

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

ans = 0

for i in range(2 ** h):
    for j in range(2 ** w):
        count = 0
        for k in range(h):
            if ((i >> k) & 1):
                for l in range(w):
                    if ((j >> l) & 1):
                        if masume[k][l]=="
                            count += 1
        if count == t:
            ans += 1

print(ans)

Solution (Python):
import numpy as np
import itertools

h, w, k = list(map(int, input().split()))
def convert(char):
  if char == '.':
    return 0
  else:
    return 1

def add_elements(c, row, column):
  s = 0
  for i in range(h):
    for j in range(w):
      if (i not in row) and (j not in column):
        s += c[i,j]
  return s

c = np.empty((h, w))

ans = 0

for i in range(h):
  line = list(map(convert, list(input())))
  c[i,:] = np.array(line)

for i in range(h+1):
  for j in range(w+1):
    rows = list(itertools.combinations(range(h),i))
    columns = list(itertools.combinations(range(w),j))
    for row in rows:
      for column in columns:
        s = add_elements(c, row, column)
        if s == k:
          ans += 1

print(ans)

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

for a in range(2**h):
    sa="0"+str(h)+"b"
    la=list(format(a,sa))
    for b in range(2**w):
        sb = "0" + str(w) + "b"
        lb = list(format(b, sb))
        cnt=0
        for i in range(h):
            for j in range(w):
                if la[i]!="1" and lb[j]!="1" and c[i][j]=="
                    cnt+=1
        if cnt==k:
            ans+=1
print(ans)

Solution (Python):
import copy


def main():
    h, w, k = [int(e) for e in input().split()]
    C = [list(input()) for i in range(h)]

    ans = 0
    for hi in range(2 ** h):
        hib = format(hi, f'0{h}b')
        for wi in range(2 ** w):
            wib = format(wi, f'0{w}b')

            CC = copy.deepcopy(C)
            for hci, hc in enumerate(hib):
                for wci, wc in enumerate(wib):

                    if hc == '1':
                        CC[hci] = ['r'] * w

                    if wc == '1':
                        for cc in CC:
                            cc[wci] = 'r'

            if sum([cc.count('
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import copy
h,w,k=map(int,input().split())
c=np.empty((h,w), dtype=int)
for i in range(h):
    s=np.array(list(input()))
    c[i,:]=np.where(s=="

ans=0
loop=0
for i in range(2**h):
    tmp=copy.deepcopy(c)
    for j in range(h):
        if (i>>j)&1:
            tmp[j,:]=0
    
    for p in range(2**w):
        tmp1=copy.deepcopy(tmp)
        for q in range(w):
            if (p>>q)&1:
                tmp1[:,q]=0
        if tmp1.sum()==k:
            ans+=1
print(ans)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,k=nii()
c=[list(input()) for i in range(h)]

black=0
for i in c:
  black+=i.count('

ans=0
for th in range(2**h):
  for tw in range(2**w):
    h_use=[]
    for i in range(h):
      if (th>>i)&1:
        h_use.append(i)
    w_use=[]
    for i in range(w):
      if (tw>>i)&1:
        w_use.append(i)

    t_cnt=0
    for i in h_use:
      t_cnt+=c[i].count('
    for i in w_use:
      for z in range(h):
        if c[z][i]=='
          t_cnt+=1
    for i in h_use:
      for j in w_use:
        if c[i][j]=='
          t_cnt-=1

    if black-t_cnt==k:
      ans+=1

print(ans)

Solution (Python):
import numpy as np
import copy
import sys

h,w,k = map(int, input().split())
C = np.array([[int(elm=="

ans = 0
for i in range(2**h):
    for ii in range(2**w):
        g = copy.deepcopy(C)
        for j in range(h):
            if i>>j &1: g[j,:] = 0
        for jj in range(w):
            if ii>>jj &1: g[:,jj] = 0
        cnt = np.count_nonzero(g)
        if cnt == k: ans += 1
print(ans)

Solution (Python):
import itertools
a = input().split(" ")
row = list(itertools.product([0,1],repeat=int(a[0])))
column = list(itertools.product([0,1],repeat=int(a[1])))
field = []
for i in range(int(a[0])):
    field.append(list(input()))

b = len(row)
c = len(column)
row_m = []
column_m = []
all = 0
for i in range(int(a[0])):
    count = 0
    for j in range(int(a[1])):
        if field[i][j] == "
            count += 1
            all += 1
    row_m.append(count)

for i in range(int(a[1])):
    count = 0
    for j in range(int(a[0])):
        if field[j][i] == "
            count += 1
    column_m.append(count)
result = 0
for i in row:
    for j in column:
        mainasu = 0

        for k in range(len(i)):
            if i[k] == 1:
                for l in range(len(j)):
                    if j[l] == 1:
                        if field[k][l] == "
                            mainasu += 1
        
        row_num = sum([x*y for (x,y) in zip(i,row_m)])
        column_num = sum([x*y for (x,y) in zip(j,column_m)])
        if int(a[2]) == all - (row_num+column_num - mainasu):
            result += 1
print(result)

Solution (Python):
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for _ in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case 


def count_black(subset, c):
    black = total_black
    for i in range(len(c)):
        if i in subset:
            for item in c[i]:
                if '
                    black -= 1

    for i in range(len(c[0])):
        if len(c) + i in subset:
            for j in range(len(c)):
                if j not in subset:
                    if '
                        black -= 1
    return black


def candidates(subset, k, c):
    start_at = 0 if len(subset) == 0 else subset[-1] + 1
    go_to = len(c) + len(c[0])
    for i in range(start_at, go_to):
        yield subset + [i]


solutions = 0
def backtrack(subset, k, c):
    curr = count_black(subset, c)
    if curr < k:
        return
    if curr == k:
        global solutions
        solutions += 1
    for cand in candidates(subset, k, c):
        backtrack(cand, k, c)


def solve(h, w, k, c):
    backtrack([], k, c)
    return solutions


total_black = 0
if __name__ == "__main__":
    h, w, k = arr_in()
    c = []
    for _ in range(h):
        c.append(str_in())
        total_black += c[-1].count("
    out(solve(h, w, k, c))

Solution (Python):
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache
from numba import jit

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	h, w, k = LI()
	grid = GRIDfromString(h,w)
	ans = 0
	cnt = 0
	for i in range(h):
		for j in range(w):
			h_comb = list(itertools.combinations(list(range(h)),i))
			w_comb = list(itertools.combinations(list(range(w)),j))
			if i == 0 and j == 0:
				if np.count_nonzero(grid == b'
					ans += 1
			elif i == 0 and j > 0:
				for w_omits in w_comb:
					if np.count_nonzero(np.delete(grid,list(w_omits),1) == b'
						ans += 1
			elif i > 0 and j == 0:
				for h_omits in h_comb:
					if np.count_nonzero(np.delete(grid,list(h_omits),0) == b'
						ans += 1
			else:
				for h_omits in h_comb:
					grid_tmp = np.delete(grid,list(h_omits),0)
					for w_omits in w_comb:
						if np.count_nonzero(np.delete(grid_tmp,list(w_omits),1) == b'
							ans += 1
	print(ans)




if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import copy
h, w, k = map(int, input().split())
table = [list(input()) for _ in range(h)]
ans = 0
for ptr_h in itertools.product([0, 1], repeat=h):
    for ptr_w in itertools.product([0, 1], repeat=w):
        times = 0
        tmp = copy.deepcopy(table)
        for i, v in enumerate(ptr_w):
            if v == 1:
                for p in tmp:
                    p[i] = "red"
        for i, v in enumerate(ptr_h):
            if v == 1:
                for ind, l in enumerate(tmp):
                    if ind == i:
                        for n in range(w):
                            l[n] = "red"
        for i in tmp:
            for j in i:
                if j == "
                    times += 1
        if times == k:
            ans += 1
print(ans)

Solution (Python):
import itertools
import decimal
import math
import collections
import sys
input = sys.stdin.readline
import copy









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

    s=[list(map(str,list(input()))) for i in range(H)]

    lisH= [num for num in range(1,H+1)]
    resultH = []
    for n in range(1,len(lisH)+1):
        for conb in itertools.combinations(lisH, n):
            resultH.append(list(conb))
    resultH.append([0])

    lisW= [num for num in range(1,W+1)]
    resultW = []
    for n in range(1,len(lisW)+1):
        for conb in itertools.combinations(lisW, n):
            resultW.append(list(conb))
    resultW.append([0])

    ans=0
    for h in range(len(resultH)):
        paintH=resultH[h]
        for w in range(len(resultW)):
            paintW=resultW[w]
            tmp=copy.deepcopy(s)
            for delH in paintH:
                if(delH!=0):
                    for i in range(W):
                        tmp[delH-1][i]="."
            for delW in paintW:
                if(delW!=0):
                    for i in range(H):
                        tmp[i][delW-1]="."  
            Cnt=0
            for i in range(H):
                Cnt+=tmp[i].count("
            if(Cnt==K):
                ans+=1
            

    print(ans) 



resolve()

Solution (Python):
h, w, K = map(int, input().split())
a = []
g = 0
for i in range(h):
    a.append(input())
for i in range(2**h):
    b = h-1
    c = []
    while i > 0:
        if i%2 == 1:
            c.append(b)
        i //= 2
        b -= 1
    for j in range(2**w):
        d = w-1
        e = []
        while j > 0:
            if j%2 == 1:
                e.append(d)
            j //= 2
            d -= 1
        f = 0
        for k in c:
            for l in e:
                if a[k][l] == "
                    f += 1
        if f == K:
            g += 1
print(g)

Solution (Python):
def dfs4(bi, a):
    res = 0
    for j in range(len(a)):
        for i in range(W):
            if bi[i] == 1 and a[j][i] == '
                res += 1
    if res == K:
        ans[0] += 1
    return

def dfs3(bi, a):
    if len(bi) == W:
        return dfs4(bi, a)
    for i in range(2):
        bi.append(i)
        dfs3(bi, a)
        bi.pop()
    return

def dfs2(bits):
    a = []
    for i in range(H):
        if bits[i] == 1:
            a.append(maze[i])
    dfs3([], a)
    
    return

def dfs(bits):
    if len(bits) == H:
        return dfs2(bits)
    for i in range(2):
        bits.append(i)
        dfs(bits)
        bits.pop()
    return

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

ans = [0]
dfs([])
print(ans[0])

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

def readinput():
    h,w,k=list(map(int,input().split()))
    c=[]
    for _ in range(h):
        l=list(input())
        c.append(l)
    return h,w,k,c

def main(h,w,k,c):
    gyo=[]
    for i in range(1,h+1):
        for cmb in combinations(range(1,h+1),i):
            gyo.append(cmb)
    gyo.append(())

    retsu=[]
    for i in range(1,w+1):
        for cmb in combinations(range(1,w+1),i):
            retsu.append(cmb)
    retsu.append(())

    ans=0
    for g in gyo:
        for r in retsu:
            cc=deepcopy(c)
            
            
            
            for i in g:
                for j in range(1,w+1):
                    cc[i-1][j-1]='*'

            for j in r:
                for i in range(1,h+1):
                    cc[i-1][j-1]='*'
            
            count=0
            for i in range(1,h+1):
                for j in range(1,w+1):
                    if cc[i-1][j-1]=='
                        count+=1
            if count==k:
                ans+=1

    return ans

if __name__=='__main__':
    h,w,k,c=readinput()
    ans=main(h,w,k,c)
    print(ans)

Solution (Python):
import numpy as np
import copy
H,W,K = map(int,input().split())
C = []
for i in range(H):
    array = []
    temp = input()
    
    array = [1 if i == '
    C.append(array)

C = np.array(C)
ans = 0
for i in range(2 ** H):
    for j in range(2 ** W):
        temp = copy.deepcopy(C)
        temp = temp.T
        for k in range(W):
            if((j>>k)&1):
                
                temp[k] = [0 for l in range(H)]
        temp = temp.T
        for k in range(H):
            if((i>>k)&1):
                
                temp[k] = [0 for m in range(W)]
    
        if sum(temp.flatten()) == K :
            ans = ans+1

print(ans)

Solution (Python):



import sys
import itertools
import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    H, W, K = i2nn()
    c = [None] * H
    for i in range(H):
        c[i] = [int(s == '
    ans = 0
    p1 = np.array(c)
    for h, w in itertools.product(range(H), range(W)):
        for row in itertools.combinations(range(H), h):
            p2 = p1.copy()
            for i in row:
                p2[i, :] = 0
            for col in itertools.combinations(range(W), w):
                p3 = p2.copy()
                for j in col:
                    p3[:, j] = 0
                if (p3.sum() == K):
                    ans += 1
    print(ans)
                
    return

main()

Solution (Python):
H, W, K = map(int, input().split())
table = []
for i in range(H):
    table.append(str(input()))
outer = 2**H
inner = 2**W
gyouketa  = '0'+str(H)+'b'
retuketa  = '0'+str(W)+'b'
count = 0
ans = 0
for i in range(outer):
    for j in range(inner):
        gyou = format(i, gyouketa)
        retu = format(j, retuketa)
        for h in range(H):
            if gyou[h] == '0':
                for w in range(W):
                    if retu[w] == '0' and table[h][w] == '
                        count += 1
        if count == K:
            ans += 1
        count = 0
print(ans)

Solution (Python):
import copy
from itertools import combinations

def count_sharp(a):
	count = 0
	for i in range(len(a)):
		for j in range(len(a[0])):
			if a[i][j] == '
				count += 1
	return count

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

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

h_sub = list()
for i in range(len(h) + 1):
	for con in combinations(h, i):
		h_sub.append(con)

w_sub = list()
for i in range(len(w) + 1):
	for con in combinations(w, i):
		w_sub.append(con)

count = 0
for h in h_sub:
	for w in w_sub:
		cc = copy.deepcopy(c)
		if len(h) != 0:
			for hh in h:
				width = len(cc[0])
				for j in range(width): cc[hh][j] = 'r'
		if len(w) != 0:
			for ww in w:
				height = len(cc)
				for i in range(height):
					cc[i][ww] = 'r'
		if count_sharp(cc) == K:
			count += 1

print(count)

Solution (Python):
import numpy as np
H,W,K = (int(x) for x in input().split())
Tile = np.zeros((H,W),dtype=bool)
Count = 0
for T in range(0,H):
    Tile[T,:] = np.array([True if I=='
for TT in range(0,pow(2,H)):
    DrawG = list(int(x) for x in list(('{:0'+str(H)+'b}').format(TT,'b')))
    GTile = np.copy(Tile)
    for TH in range(0,H):
        if DrawG[TH]==1:
            GTile[TH,:] = False
    for TTT in range(0,pow(2,W)):
        WTile = np.copy(GTile)
        DrawL = list(int(x) for x in list(('{:0'+str(W)+'b}').format(TTT,'b')))
        for TTW in range(0,W):
            if DrawL[TTW]==1:
                WTile[:,TTW] = False
        if np.sum(WTile)==K:
            Count += 1
print(Count)

Solution (Python):
H,W,K = map(int,input().split())
L = []
for _ in range(H):
    l = list(input())
    L.append(l)
import copy
ans =0
for x in range(2 ** H):
    for y in range(2 ** W):
        c = copy.deepcopy(L)

        for i in range(H):
            if x & (1 << i):
                for yoko in range(W):
                    c[i][yoko] = '.'
        for j in range(W):
            if y & (1 << j):
                for tate in range(H):
                    c[tate][j] = '.'
        
        cnt = 0
        for i in range(H):
            for j in range(W):
                if c[i][j] == '
        if cnt == K:
            ans += 1

print(ans)

Solution (Python):

import numpy as np

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

rst = 0
for i in range(pow(2, h)):
    h_mask = np.array(list(map(lambda x: x == "0", ("000000" + bin(i)[2:])[-h:])))
    _c = c[h_mask].T
    for j in range(pow(2, w)):
        w_mask = np.array(list(map(lambda x: x == "0", ("000000" + bin(j)[2:])[-w:])))
        if len(_c) == 0:
            count = 0
        else:
            __c = _c[w_mask]
            count = np.count_nonzero(__c == '
        if k == count:
            rst += 1

print(rst)

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



def check(a, p_r, p_c):
    a2 = a.copy()
    for i, s in enumerate(p_r):
        if s=='1':
            a2[i] = 'r'
    for i, s in enumerate(p_c):
        if s=='1':
            a2[:,i] = 'r'

    return np.sum(a2=='



result = 0
n = H+W
for i in range(2**n):
    pattern = format(i, '0%db'%n)
    p_r = pattern[:H]
    p_c = pattern[H:]
    if check(a, p_r, p_c) == K:
        result += 1

print(result)

Solution (Python):
import itertools

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

if K == H*W:
    print(1)
    exit()

b = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == "
            b += 1

r = [i for i in range(H)]
c = [i for i in range(W)]

r_comb = []
for h in range(H):
    for v in itertools.combinations(r,h):
        r_comb.append(v)
c_comb = []
for w in range(W):
    for v in itertools.combinations(c,w):
        c_comb.append(v)      

ans = 0
for R in r_comb:
    for C in c_comb:
        tmp = b

        
        for h in range(H):
            if h in R:
                tmp -= field[h].count("

        
        for h in range(H):
            if h not in R:
                for w in range(W):
                    if w in C and field[h][w] == "
                        tmp -= 1
    
        if tmp == K:
            ans += 1

print(ans)

Solution (Python):
import itertools
import copy
h, w, k = (int(x) for x in input().split())
count=0
c =[[]for i in range(h)]
for i in range(h):
	c[i]=input()
	
for i in range(h):
	for j in range(w):
		if c[i][j]=="
			count+=1
ans = 0
need = count-k

for i in itertools.product([0,1], repeat=h):
	need1 = need
	c_2 = copy.copy(c)
	for j in range(h):
		if i[j]==1:
			for k in range(w):
				if c_2[j][k]=="
					need1-=1
			list = ["."]*w
			c_2[j]="".join(list)
					
					
	for j in itertools.product([0,1], repeat=w):
		need2=need1
		for k in range(w):
			if j[k]==1:
				for l in range(h):
					if c_2[l][k]=="
						need2-=1
		if need2==0:
			ans+=1
print(ans)

Solution (Python):
from itertools import product
h,w,k = map(int, input().split())
a =[]
for i in range(h):
  a.append(input().split())
f=list(product([0,1], repeat=h))
f2=list(product([0,1], repeat=w))
b=0
su=0
for i in f:
    for j in f2:
        for i2 in range(h):
            for j2 in range(w):
                if i[i2]==0 and j[j2]==0:
                    if a[i2][0][j2]=="
                        b+=1
        if b==k:
            su+=1
        b=0
print(su)

Solution (Python):
H, W, K = map(int, input().split())
cc = [list(input()) for _ in range(H)]
c = [c[:] for c in [[''] * W] * H]
ans = 0
for h in range(2**H):
    for w in range(2**W):
        for i in range(H):
            for j in range(W):
                 c[i][j] = cc[i][j]            
        for i in range(H):
            if ((h >> i) & 1):
                for jj in range(W):
                    c[i][jj] = "!"
        for j in range(W):
            if ((w >> j) & 1):
                for ii in range(H):
                    c[ii][j] = "!"
        black = 0
        for i in range(H):
            for j in range(W):
                 if c[i][j] == '
                    black += 1
        if black == K:
            ans += 1
print(ans)