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 numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]

h,w,k = imap()
grid = np.array([[int(elm=="

ans = 0
for i in range(2**h):
    for ii in range(2**w):
        g = cp.deepcopy(grid)
        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):

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


c = [list(map( list,input().split())) for l in range(h)]
t=0


for i in range (2**h):
   a = [0] * w
   for p in range(h):
      for q in range(w):
         if c[p][0][q] == "
            if i//(2**p)%2==0:
               a[q]+=1
   for m in range(2**w):
      kk=0
      for j in range(w):
         if m//(2**j)%2==0:
            kk+=a[j]
      if k==kk:
         t+=1

print(t)

Solution (Python):
import copy

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

matrix = [[0 for i in range(w)] for j in range(h)]

def delRow(a, mat):
    for i in range(w):
        mat[a][i] = 0

def delCol(b, mat):
    for j in range(h):
        mat[j][b] = 0

def sum2d(mat):
    s = 0
    for i in range(len(mat)):
        for j in range(len(mat[i])):
            s += mat[i][j]
    return s

for i in range(h):
    c = input()
    for j in range(w):
        if c[j] == '
            matrix[i][j] += 1


for i in range(2 ** h):
    for j in range(2 ** w):
        mat = copy.deepcopy(matrix)
        for l in range(h):
            if ((i >> l) & 1):
                delRow(l, mat)
        for l in range(w):
            if ((j >> l) & 1):
                delCol(l, mat)
        if sum2d(mat) == k:
            ans += 1
print(ans)

Solution (Python):
import numpy as np
from itertools import product
H, W, K = map(int, input().split())

C = [None] * H
for i in range(H):
    C[i] = input()

np_c = np.zeros((H, W), dtype=int)
for i in range(H):
    for j in range(W):
        if C[i][j] == "
            np_c[i][j] = 1


ans = 0
for h_bin in product([True, False], repeat = H):
    for w_bin in product([True, False], repeat = W):
        copy_array = np_c.copy()
        for i, h in enumerate(h_bin):
            for j, w in enumerate(w_bin):
                if h:
                    copy_array[i, :] = 0
                if w:
                    copy_array[:, j] = 0
        if copy_array.sum() == K:
            ans += 1

print(ans)

Solution (Python):

import numpy as np
import itertools
from copy import deepcopy

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

Arr = np.zeros((H, W))
for i in range(H):
    words = input()
    for j, w in enumerate(words):
        if w == "
            Arr[i,j] = 1

ans = 0
for t in range(0,H+W):
    Ex = list(itertools.combinations([int(i) for i in range(H+W)],t))
    for j in Ex:
        TMP = deepcopy(Arr)
        for num in j:
            if num < H:
                TMP[num] = np.zeros(W)
            else:
                w = num - H
                
                TMP[:,w] = np.zeros(H)
                
        if K == int(np.sum(TMP)):
            ans += 1
print(ans)

Solution (Python):
import sys
import os
import itertools
import numpy as np
from collections import deque
import copy

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    
    ans=0
    W_list = []
    for j in range(W+1): 
        W_list.extend(list(itertools.combinations([i for i in range(W)],j)))

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

    for W_set in W_list:
        for H_set in H_list:
            
            tmp=copy.copy(C)
            
            
            
            for w in W_set:
                
                for i in range(H):
                    
                    tmp[i]=tmp[i][:w]+'.'+tmp[i][w+1:]

            for h in H_set:
                for i in range(W):
                    tmp[h]=tmp[h][:i]+'.'+tmp[h][i+1:]

            count = 0
            for w in range(W):
                for h in range(H):
                    if tmp[h][w]=='
                        count+=1

            if count == K:
                ans+=1

    print(ans)

if __name__ == '__main__':
    main()

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

    ans = 0
    for a in range(2**h):
        for b in range(2**w):
            black_sum = 0
            row = list(format(a,'0'+str(h)+'b'))
            column = list(format(b,'0'+str(w)+'b'))
            for i in range(h):
                if row[i] == '1':
                    continue
                for j in range(w):
                    if column[j] == '1':
                        continue
                    elif c[i][j] == "
                        black_sum += 1
            if black_sum == k:
                ans += 1
        
    print(ans)

resolve()

Solution (Python):
import numpy as np
import math
H,W,K = map(int,input().split())
m = []
for i in range(H):
    m.append(list(input()))
m = np.array(m)
bcell = m=="

ans = 0
for i in range(2**H):
    r_pattern = np.array(list(format(i, f'0{H}b')))=='1'
    for j in range(2**W):
        c_pattern = np.array(list(format(j, f'0{W}b')))=='1'
        mask = r_pattern.reshape(H,1) & c_pattern.reshape(1,W)
        
        b_cell_num = np.sum(bcell&mask)
        if b_cell_num ==K:
            ans +=1
print(ans)

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

buf = []
total = 0
for row in range(h):
    row = list(input())

    buf.append(row)

    total += row.count('

colors = list(zip(*buf))

if k > total:
    print(0)
    exit()


diff = total - k

candH = 2 ** h
candW = 2 ** w


def counting(text):
    res = []
    for i, c in enumerate(text):
        if c == '
            res.append(i)
    return res

ans = 0
for a in range(candH):
    for b in range(candW):
        hBit = a
        wBit = b
        currentCount = 0

        hIndexList = []
        for r in range(h):
            shouldAgg = hBit % 2 == 1
            hBit = hBit >> 1

            l = []
            if shouldAgg:
                l = counting(buf[r])
            hIndexList.append(l)
            currentCount += len(l)

        for c in range(w):
            shouldAgg = wBit % 2 == 1
            wBit = wBit >> 1

            if shouldAgg:
                cIndex = counting(colors[c])
                currentCount += len(cIndex)

                for ci in cIndex:
                    if c in hIndexList[ci]:
                        currentCount -= 1

        if currentCount == diff:
            ans += 1


print(ans)

Solution (Python):
import copy

H,W,K=map(int,input().split())
C=[]
for i in range(H):
    C.append(list(input()))
Ans=0
for i in range(2**H):
    IDh=format(i,"b").zfill(H)
    for j in range(2**W):
        n=0
        IDw=format(j,"b").zfill(W)
        c=copy.deepcopy(C)
        for k in range(H):
            if IDh[k]=="1":
                c[k]=["!" for i in range(W)]
        for k in range(W):
            if IDw[k]=="1":
                for l in range(H):
                    c[l][k]="!"
        for k in range(H):
            for l in range(W):
                if c[k][l]=="
                    n+=1
        if n==K:
            Ans+=1
print(Ans)

Solution (Python):
import sys

[H,W,K]=[int(i) for i in sys.stdin.readline().split()]

arr=[]

for x in range(H):
	tmp=sys.stdin.readline().strip()
	arr.append(tmp)

rows=[0]*H
cols=[0]*W

total=0

for g in range(H):
	su=0
	for h in range(W):
		if(arr[g][h]=="
			su+=1
			total+=1
	rows[g]=su

for p in range(W):
	su2=0
	for q in range(H):
		if(arr[q][p]=="
			su2+=1
	cols[p]=su2

n1=pow(2,H)
n2=pow(2,W)

ans=0

for a in range(n1):
	for b in range(n2):
		rs=bin(a)[2:]
		cs=bin(b)[2:]
		
		rs="0"*(H-len(rs))+rs
		cs="0"*(W-len(cs))+cs

		num=total

		for p in range(len(rs)):
			if(rs[p]=="1"):
				num-=rows[p]

		for q in range(len(cs)):
			if(cs[q]=="1"):
				num-=cols[q]
				for g in range(len(rs)):
					if(rs[g]=="1" and arr[g][q]=="
						num+=1

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

print(ans)

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

ans = 0

c_h = [ 0 for _ in range( h ) ] 
c_w = [ 0 for _ in range( w ) ] 
all_black = 0

for i in range( h ):
    for j in range( w ):
        if c[ i ][ j ] == "
            c_h[ i ] += 1
            c_w[ j ] += 1
            all_black += 1

def count_black( list_h, list_w ):
    cnt = all_black
    for i in list_h:
        cnt -= c_h[ i ]
    for j in list_w:
        cnt -= c_w[ j ]
    for i in list_h:
        for j in list_w:
            if c[ i ][ j ] == "
                cnt += 1
    return cnt

def solve( i, list_h, j, list_w ):
    if i < h:
        solve( i + 1, list_h, j, list_w )
        solve( i + 1, list_h + [ i ], j, list_w )
    else:
        if j < w:
            solve( i, list_h, j + 1, list_w )
            solve( i, list_h, j + 1, list_w + [ j ] )
        else:
            if k == count_black( list_h, list_w ):
                global ans
                ans += 1

solve( 0, [], 0, [] )
print( ans )

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

def count(C0, H, W, hl, wl):
    T = [['' for i in range(W)] for j in range(H)]
    for i in range(H):
        for j in range(W):
            T[i][j] = C[i][j]       

    for j in hl:
        for i in range(W):
            T[j][i] = 'R'
    for i in wl:
        for j in range(H):
            T[j][i] = 'R'

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

ans = 0
for j in range(W+1):
    for w in itertools.combinations(list(range(W)), j):
        for i in range(H+1):
            for v in itertools.combinations(list(range(H)), i):
                r = count(C, H, W, list(v), list(w))
                if r == K:
                    ans += 1
print(ans)

Solution (Python):
""" C
    https://atcoder.jp/contests/abc173/tasks/abc173_c
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def _pattern(N):
    if N > 1:
        pa = _pattern(N-1)
        return [[0] + p for p in pa] + [[1] + p for p in pa]
    else:
        return [[0], [1]]

def main(H, W, K, c):
    count = 0
    pwSet = _pattern(W)
    phSet = _pattern(H)
    for ph in phSet:
        result = []
        for i in range(0, len(ph)):
            if ph[i] == 1:
                result.append(c[i])
        for pw in pwSet:
            s = 0
            for r in result:
                s += sum([1 if r[j] == "
            if s == K:
                count += 1
    return count

if __name__ == "__main__":
    _H, _W, _K = readIntegerSet(3)
    _c = [list(readString().strip()) for _ in range(0, _H)]

    print(main(_H, _W, _K, _c))

Solution (Python):
from itertools import combinations

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

black = 0
for wli in cli:
    black += wli.count('


answer = 0
for i in range(h+w+1):
    combis = list(combinations(range(1,h+w+1),i))

    
    for combi in combis:
        tmp_black = black
        red_row = []
        red_column = []
        for red in combi:
            if 1 <= red <= h:
                red_row.append(red-1)
            elif h+1 <= red <= h+w:
                red_column.append(red-h-1)

        for j, wli in enumerate(cli):
            if j in red_row:
                tmp_black -= wli.count('
                continue

            for r in red_column:
                if wli[r] == '
                    tmp_black -= 1
            
        if tmp_black == k:
            answer += 1

print(answer)

Solution (Python):
import copy

def find(h):
    bits_active = {}
    for i in range(pow(2,h)):
        x = bin(i)[2:]
        if len(x) < h:
            x = '0'*(h-len(x))+x

        ones = x.count('1')
        if ones not in bits_active.keys():
            bits_active[ones] = []

        bits_active[ones].append(x)

    return bits_active

def good(grid,h,w,row_perm,col_perm,k):
    temp = copy.deepcopy(grid)
    for i in range(h):
        if row_perm[i] == '1':
            for j in range(w):
                temp[i][j] = 'r'

    for j in range(w):
        if col_perm[j] == '1':
            for i in range(h):
                temp[i][j] = 'r'

    count = 0
    for i in range(h):
        for j in range(w):
            if temp[i][j] == '
                count += 1

    if count == k:
        return True

    return False

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

    bits_active_rows = find(h)
    bits_active_cols = find(w)
    total = 0
        
    for rows_chosen in range(h+1):
        for cols_chosen in range(w+1):
            for row_perm in bits_active_rows[rows_chosen]:
                for col_perm in bits_active_cols[cols_chosen]:
                    if good(grid,h,w,row_perm,col_perm,k):
                        total += 1

    print(total)

main()

Solution (Python):

from copy import deepcopy
from itertools import product
h, w, push = map(int, input().split())
ans = 0
an = []
a = ['@'] * w
c = []
d = []
for q in range(h):
    _ = list(input())
    c.append(_)
    d.append(_)
for H in product([0, 1], repeat=h):
    for W in product([0, 1], repeat=w):
        c = deepcopy(d)
        count = 0
        for i, j in enumerate(H):
            if j:
                c[i] = a
        for k, l in enumerate(W):
            if l:
                for x in range(h):
                    c[x][k] = '@'
        for hi in c:
            for wi in hi:
                if wi == '
                    count += 1
        an += [count]
for answer in an:
    if answer == push:
        ans += 1
print(ans)

Solution (Python):
import numpy as np
import itertools

H,W,K=map(int, input().split())
C_=[list(input()) for _ in range(H)]
C=[]
temp=[]
ans=0

for i in range(H):
	for h in range(W):
		if C_[i][h]==".":temp.append(0)
		else:temp.append(1)
	C.append(temp)
	temp=[]
C=np.array(C)

HP_=[h for h in range(H)]
HP=[]
for r in range(H):
	HP.append(list(itertools.combinations(HP_,r)))
WP_=[w for w in range(W)]
WP=[]
for r in range(W):
	WP.append(list(itertools.combinations(WP_,r)))


for i in range(len(HP)):
	for hp in HP[i]:
		C_del_wp=np.delete(C,hp,0)
		
		
		for h in range(len(WP)):
			for wp in WP[h]:
				C_del=np.delete(C_del_wp,wp,1)
				
				
				if np.count_nonzero(C_del==1)==K:
					ans+=1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
H, W, K = map(int, input().split())
C = []
for _ in range(H):
    C.append(list(input()))

ans = 0
def dfs(HSelect, WSelect):
    global ans, H, W, K
    if len(HSelect) == H and len(WSelect) == W:
        count = 0
        for j in range(W):
            for i in range(H):
                if HSelect[i] or WSelect[j]:
                    continue
                if C[i][j] == "
                    count += 1
        if count == K:
            ans += 1
        return

    Hnext = HSelect[:]
    Wnext = WSelect[:]
    if len(HSelect) < H and len(WSelect) < W:
        dfs(Hnext+[False], Wnext+[False])
        dfs(Hnext+[True], Wnext+[False])
        dfs(Hnext+[False], Wnext+[True])
        dfs(Hnext+[True], Wnext+[True])
    elif len(HSelect) < H:
        dfs(Hnext+[False], Wnext)
        dfs(Hnext+[True], Wnext)
    elif len(WSelect) < W:
        dfs(Hnext, Wnext+[False])
        dfs(Hnext, Wnext+[True])


dfs([], [])
print(ans)

Solution (Python):
import itertools
h,w,k=map(int,input().split())
C=[]
for _ in range(h):
    c=input()
    C.append(c)
l1=list(itertools.product([0,1],repeat=h))
l2=list(itertools.product([0,1],repeat=w))
count=0
for i in range(2**h):
    for j in range(2**w):
        black=0
        for ii in range(h):
            for jj in range(w):
                if l1[i][ii]==0 and l2[j][jj]==0 and C[ii][jj]=='
                    black+=1
        if black==k:
            count+=1
print(count)

Solution (Python):
import copy

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

ans = 0
for i in range(2**H):
  
  tmp = copy.deepcopy(S)      
  
  keta_i = 0
  ii = i
  while ii > 0:
    if ii & 1:
      
      for k in range(W):
        tmp[keta_i][k] = "."
    keta_i += 1
    ii = ii >> 1
  
    
  for j in range(2**W):
    tmp2 = copy.deepcopy(tmp)
    keta_j = 0
    jj = j
    while jj > 0:
      if jj & 1:
        for l in range(H):
          
          
          tmp2[l][keta_j] = "."
      keta_j += 1
      jj = jj >> 1
      
    
    count = 0
    for l in range(H):
      for k in range(W):
        if tmp2[l][k] == "
          count += 1
    
    if count == K:
      ans += 1
      
      
print(ans)

Solution (Python):
import itertools
import numpy as np

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

b = np.array([['.' for i in range(W)] for j in range(H)])

for h in range(H):
    b[h] = list(input())
    
h_conb = []
w_conb = []
for i in range(1,H+1):
    h_conb += list(itertools.combinations(range(H), i))
for i in range(1,W+1):
    w_conb += list(itertools.combinations(range(W), i))

count = 0

if K == 0:
    count += 1

for h in h_conb:
    for w in w_conb:
        
        
        if np.count_nonzero(b[list(h)][:,list(w)] == '
            count += 1

print(count)

Solution (Python):
import numpy as np
H,W,K=map(int,input().split())
s=[]
for i in range(H):
    a=list(input())
    a=[0 if moji=="." else 1 for moji in a]
    s.append(a)
s=np.array(s)
count=0
for i in range(2**H):
    l1=[]
    ss = s.copy()
    for j in range(H):
        if i>>j&1:l1.append(j)
    for height in l1:
        ss[height, :] = 0
    for k in range(2**W):
        l2=[]
        ss2=ss.copy()
        for m in range(W):
            if k>>m&1:l2.append(m)
        for width in l2:
            ss2[:,width]=0
        if np.sum(ss2)==K:
            count+=1

print(count)

Solution (Python):
h,w,k=map(int,input().split())
c=[list(input()) for i in range(h)]
black =0
for i in range(h):
  for j in range(w):
    if c[i][j]=='
      black+=1
      c[i][j]=1
    else:
      c[i][j]=0
ans=0
for i in range(2**h):
  for j in range(2**w):
    cnt = black
    for p in range(h):
      for q in range(w):
        if i >> p & c[p][q]:
          cnt-=1
          continue
        if j >> q & c[p][q]:
          cnt-=1
    if cnt == k:
      
      ans+=1
print(ans)

Solution (Python):
from sys import stdin
from itertools import product

def main():

    input = stdin.readline

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

    s = [] * H

    for _ in range(H):
        s.append(str(input())[:-1])

    ans = 0

    for h in list(product([0,1], repeat=H)):
        for w in list(product([0,1], repeat=W)):
            tmp_s = s.copy()
            count_num = 0

            for w_num in range(W):
                if w[w_num] == 1:
                    for w_s in range(H):
                        tmp_s[w_s] = tmp_s[w_s][:w_num] + "x" + tmp_s[w_s][w_num+1:]
        
            for h_num in range(H):
                if h[h_num] == 1:
                    tmp_s[h_num] = ""


            for i in tmp_s:
                count_num += i.count("

            if count_num == K:
                ans += 1


    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import copy
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))


H, W, K = LI()
c = []
for i in range(H):
    tmp_l = S()
    c.append([1 if c == "


num_pattern = 0
for h in range(2 ** H):
    format_str = "{:0" + str(H) + "b}"
    h_update = [c == "1" for c in reversed(format_str.format(h))]

    for w in range(2 ** W):
        format_str = "{:0" + str(W) + "b}"
        w_update = [c == "1" for c in reversed(format_str.format(w))]
        

        cc = copy.deepcopy(c)
        for i, flag in enumerate(h_update):
            if flag:
                cc[i] = [0 for _ in range(W)]
        for i, flag in enumerate(w_update):
            if flag:
                for j in range(H):
                    cc[j][i] = 0

        total = sum([sum(cc[i]) for i in range(H)])
        if total == K:
            num_pattern += 1

print(num_pattern)

Solution (Python):
import copy
H, W, K = map(int, input().split())
Co = [list(map(str, input())) for _ in range(H)]
ans = 0
for i in range(2 ** H):
  C = copy.deepcopy(Co)

  for j in range(H):
    if (i >> j & 1) == 1:
      for k in range(W):
        C[j][k] = ""
  for l in range(2 ** W):
    C1 = copy.deepcopy(C)
    for m in range(W):
      if (l >> m & 1) == 1:
        for n in range(H):
          C1[n][m] = ""

    cnt = 0
    for o in range(H):
      for p in range(W):
        if C1[o][p] == "
          cnt += 1
    if cnt == K:
      ans += 1
print(ans)

Solution (Python):
import itertools
import numpy as np

















H, W, K = map(int, input().split())
ARR2 = np.zeros((H, W))
for i in range(H):
    s = list(input())
    for j in range(W):
        if s[j] == ".":
            ARR2[i][j] == 0
        else:
            ARR2[i][j] = 1










def calclulate(h, w, k, arr):
    result = 0
    hIndex = [i for i in range(h)]
    wIndex = [i for i in range(w)]

    for hChooseNum in range(h + 1):
        for wChooseNum in range(w + 1):
            for m in itertools.combinations(hIndex, hChooseNum):
                for n in itertools.combinations(wIndex, wChooseNum):

                    tmpArr = arr.copy()

                    for _m in m:
                        tmpArr[_m, :] = 0
                    for _n in n:
                        tmpArr[:, _n] = 0

                    if np.sum(tmpArr == 1) == k:
                        result += 1
    print(result)


calclulate(H, W, K, ARR2)

Solution (Python):
H, W, K = map(int, input().split())
init_kuro = 0
HW = []
for i in range(H):
    t = list(input())
    k = t.count('
    HW.append(t)
    init_kuro += k



import itertools

tate = list(itertools.product([0, 1], repeat=H))
yoko = list(itertools.product([0, 1], repeat=W))

ans = 0


def solve(T, Y):
    tmp = 0
    for i, t in enumerate(T):
        if t == 1:
            for j, h in enumerate(HW[i]):
                if h == '
                    tmp += 1

    for i, y in enumerate(Y):
        if y == 1:
            for hw in HW:
               if hw[i] == '
                   tmp +=1

    if init_kuro - tmp == K:
        return 1
    else:
        return 0


ans = 0
for T in tate:
    for Y in yoko:
        ans += solve(T, Y)
print(ans)

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

ans = 0

for i in range(2**H):
    for j in range(2**W):
        c_ = copy.deepcopy(c)
        for k in range(H):
            if ((i >> k) & 1):
                for l in range(W):
                    c_[k][l] = '-'
        for k in range(W):
            if ((j >> k) & 1):
                for l in range(H):
                    c_[l][k] = '-'
        if(sum([m.count('
            ans += 1


print(ans)

Solution (Python):
import numpy

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

data = []
for i in range(H):
    data.append(list(map(lambda x: int(x == "

data = numpy.asarray(data)

result = 0
for i in range(2**H):
    
    H_matrix = numpy.asarray([int(bool(i & (1 << h))) for h in range(H)])

    for j in range(2**W):
        W_matrix = numpy.asarray([int(bool(j & (1 << w))) for w in range(W)])
        if numpy.sum((data * W_matrix).T * H_matrix) == K:
            result += 1

print(result)

Solution (Python):
from itertools import combinations as comb
h,w,k = map(int,input().split())

def check(r,c,a):
  b = 0
  for i in range(h):
    if r[i]:
      for j in range(w):
        if c[j] and a[i][j] == '
          b += 1
  return int(b==k)

a = []
for _ in range(h):
  a.append(list(input()))
row_comb = []
col_comb = []
rows = [i for i in range(h)]
cols = [i for i in range(w)]
for i in range(h+1):
  row_comb += list(comb(rows,i))
for i in range(w+1):
  col_comb += list(comb(cols,i))
ans = 0
for row in row_comb:
  for col in col_comb:
    r = [True]*h
    c = [True]*w
    for i in row:
      r[i] = False
    for i in col:
      c[i] = False
    ans += check(r,c,a)
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
import numpy as np
mod = 10 ** 9 + 7
H, W, K = MAP()
L = [input() for i in range(H)]
S = [[0] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if L[i][j] == "
            S[i][j] = 1
S_n = np.array(S)

import itertools
L = [0, 1] 


h_b = list(itertools.product([0, 1], repeat=H))
w_b = list(itertools.product([0, 1], repeat=W))


mask = [[0] * W for i in range(H)]

cnt = 0

for h_t in h_b:
    for w_t in w_b:
        for i, h_ in enumerate(h_t):
            for j, w_ in enumerate(w_t):
                mask[i][j] = h_ * w_
        m_n = np.array(mask)
        ada = np.sum(m_n * S_n)
        if ada == K:
            cnt += 1
print(cnt)

Solution (Python):
import itertools
h,w,k = map(int, input().split())
c = []
for i in range(h):
    a = input()
    for j in range(w):
        if a[j] == '
            c.append((i,j))

ans = 0

sel = ['h'+str(i) for i in range(h)]
sel += ['w'+str(i) for i in range(w)]
for m in range(h+w):
    for v in  itertools.combinations(sel,m):
        count = [1 for kk in range(len(c))]
        for vv in v:
            if vv[0]=='h':
                for e,(i,j) in enumerate(c):
                    if i == int(vv[1]):
                        count[e] = 0
            if vv[0]=='w':
                for e,(i,j) in enumerate(c):
                    if j == int(vv[1]):
                        count[e] = 0
        if sum(count) == k:
            ans += 1


print(ans)

Solution (Python):
from itertools import product

H, W, K = map(int, input().split())
tiles = []
n = 0
for h in range(H):
    row = list(input())
    tiles.append(row)

cols, rows = [0] * W, [0] * H
for x in range(W):
    c = 0
    for y in range(H):
        if tiles[y][x] == "
            c += 1
    cols[x] = c
for y in range(H):
    c = 0
    for x in range(W):
        if tiles[y][x] == "
            c += 1
    rows[y] = c
n = sum(cols)

count = 0
for hy in product([0, 1], repeat=H):
    for hx in product([0, 1], repeat=W):
        c = set()
        for i, fy in enumerate(hy):
            if fy:
                for x in range(W):
                    if tiles[i][x] == "
                        c.add((x, i))
        for j, fx in enumerate(hx):
            if fx:
                for y in range(H):
                    if tiles[y][j] == "
                        c.add((j, y))
        if n - len(c) == K:
            count += 1
print(count)

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


i_list=[i for i in range(H)]
j_list=[j for j in range(W)]

for i in range(H+1):
    i_ = list(itertools.combinations(i_list, i))
    for j in range(W+1):
        j_ = list(itertools.combinations(j_list, j))
        
        
        for ii in i_: 
            for jj in j_:
                count=0
                
                
                
                for iii in range(H):
                    for jjj in range(W):
                        if c[iii][jjj]=="
                            
                            count+=1
                
                if count==K:
                    ans+=1
print(ans)