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):
H,W,K = map(int, input().split())

edge = [["
center = [["

c = edge + center + edge

N = H + W
ans = 0

for i in range(2**(N)):
    bit_array = str(bin(i)[2:]).zfill((N))
    
    black = 0
    
    H_bit = [0] + list(bit_array[0:H])
    W_bit = [0] + list(bit_array[H:])
    

    for j in range(1,H+1):
        if H_bit[j] != "1":
            for k in range(1,W+1):
                if W_bit[k]!="1" and c[j][k]=="
                    black += 1
        if black > K:
            break
    
    if black == K:
        ans += 1

print(ans)

Solution (Python):
from itertools import product as pro

h,w,K=map(int,input().split())
C=[]
for _ in range(h):
    C.append(list(str(input())))



L=['0','1']
Sh=pro(L,repeat=h)


ans=0
for i in Sh:
    Sw=pro(L,repeat=w)
    for j in Sw:
        temp=0

        for k in range(h):
            for l in range(w):
                if i[k]=='0' and j[l]=='0':
                    if C[k][l]=='
                        temp+=1
        
        if temp==K:
            ans+=1
           

print(ans)

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

ans = 0
for i in range(1<<H):
    for j in range(1<<W):
        cnt = 0
        for k in range(H):
            for l in range(W):
                if i & 1 << k or j & 1 << l: continue
                if c[k][l] == '
                    cnt += 1
        
        if cnt == K:
            ans += 1

print(ans)

Solution (Python):
import itertools
h, w, k = map(int, input().split())
s = []

total = 0
hcnt = [0 for i in range(h)]
wcnt = [0 for i in range(w)]
for i in range(h):
  c = input()
  hcnt[i] = c.count('
  total += c.count('
  s.append(c)

for i in range(w):
  cnt = 0
  for j in range(h):
    if s[j][i] == '
      cnt += 1
  wcnt[i] = cnt

ans = 0
for i in itertools.product([0,1], repeat=h):
  for j in itertools.product([0,1], repeat=w):
    cnt = 0
    for a in range(h):
      for b in range(w):
        if i[a] == 1 and j[b] == 1:
          if s[a][b] == '
            cnt += 1
    if cnt == k:
      ans += 1
print (ans)

Solution (Python):
H,W,K = map(int,input().split())
C = []
for _ in range(H):
    C.append(input())
res = 0
for i in range(2**W):
    for j in range(2**H):
        tmp = 0
        for h in range(H):
            for w in range(W):
                if bin(i)[2:].zfill(W)[w] == '0' and bin(j)[2:].zfill(H)[h] == '0' and C[h][w] == '
                    tmp += 1
        if tmp == K:
            res += 1

print(res)

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

H,W,K=map(int,input().split())
c=np.array([list(input()) for _ in range(H)])
red_h=np.array(["R"]*W)
red_w=np.array(["R"]*H).reshape((H,1))

ans=0
for i in range(2**H):
    tmp1=copy(c)
    for j in range(H):
        if i%2==1:
            tmp1[j,:]=red_h
        i//=2
    for k in range(2**W):
        tmp2=copy(tmp1)
        cnt=0
        for l in range(W):
            if k%2==1:
                tmp2[:,l]=red_w[:,0]
            k//=2
    
        for h in range(H):
            for w in range(W):
                if tmp2[h,w]=="
                    cnt+=1
        if cnt==K:
            ans+=1
print(ans)

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def bit_indexes(x):
    i = 0
    while x != 0:
        if x%2 != 0:
            yield i
        x //= 2
        i += 1
    

def solve():
    H, W, K = read_ints()
    C = []
    black_count = 0
    for i in range(H):
        C.append(input().strip())
        black_count += C[-1].count('
    ans = 0
    for i in range(2**H):
        for j in range(2**W):
            count = black_count
            for i0 in bit_indexes(i):
                for j0 in range(W):
                    if C[i0][j0] == '
                        count -= 1
            for j0 in bit_indexes(j):
                for i0 in range(H):
                    if C[i0][j0] == '
                        count -= 1
            for i0 in bit_indexes(i):
                for j0 in bit_indexes(j):
                    if C[i0][j0] == '
                        count += 1
            if count == K:
                ans += 1
    return ans


if __name__ == '__main__':
    print(solve())

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

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

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

pset = product(powerset(range(h)), powerset(range(w)))
ans = 0
for vert, hori in pset:
    D = deepcopy(C)
    for i in vert:
        for j in range(w):
            D[i][j] = 'r'
    for i in range(h):
        for j in hori:
            D[i][j] = 'r'
    count = sum(D[i].count('
    if count == k:
        ans += 1
print(ans)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd, cos, radians, floor
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



h, w, k2 = map(int, input().split())
c = [[j for j in input()] for i in range(h)]
ans = 0
for i in range(1 << (h + w)):
    bit = bin(i)[2:].zfill(h + w)
    bit1 = bit[:h]
    bit2 = bit[h:]
    cnt = [[0 for _ in range(w)] for _ in range(h)]
    for j in range(h):
        if bit1[j] == "1":
            for k in range(w):
                cnt[j][k] = 1
    for j in range(w):
        if bit2[j] == "1":
            for k in range(h):
                cnt[k][j] = 1
    
    cnt2 = 0
    for j in range(h):
        for k in range(w):
            if c[j][k] == "
                cnt2 += 1
    if cnt2 == k2:
        
        
        
        
        
        

        
        
        
        
        
        
        ans += 1
print(ans)

Solution (Python):
import copy

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

hpattern = []
for i in range(2 ** h):
    temp = [0] * h
    for j in range(h):
        if i >> j & 1:
            temp[j] = 1
    hpattern.append(temp)

wpattern = []
for i in range(2 ** w):
    temp = [0] * w
    for j in range(w):
        if i >> j & 1:
            temp[j] = 1
    wpattern.append(temp)

ans = 0
for hp in hpattern:
    for wp in wpattern:
        cc = copy.deepcopy(c)
        for i in range(h):
            for j in range(w):
                if hp[i] == 1:
                    cc[i][j] = -1
                if wp[j] == 1:
                    cc[i][j] = -1

        black = sum([l.count('
        if black == k:
            ans += 1

print(ans)

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

for i in range(h):
    for j in range(w):
        if c[i][j]=="
            sumb+=1
ans=0
for i in range(2**(h+w)):
    lish,lisw=[],[]
    s=sumb
    for j in range(h+w):
        if (i>>j)&1:
            if j<h:
                lish.append(j)
            else:
                lisw.append(j-h)
    for idxh in lish:
        for idx in range(w):
            s=s-(c[idxh][idx]=="
    for idx in range(h):
        for idxw in lisw:
            s=s-(c[idx][idxw]=="
    for idxh in lish:
        for idxw in lisw:
            s+=(c[idxh][idxw]=="
    if s==k:
        ans+=1
print(ans)

Solution (Python):
from collections import deque

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

mp = [input() for _ in range(H)]
h = deque([[[0],[0]], [[0],[1]], [[1],[0]], [[1],[1]]])

rlt = 0
while h:
  l = h.pop()
  if len(l[0]) == H and len(l[1]) == W:
    k = 0
    for i in range(H):
      if l[0][i] == 1:
        continue
      for j in range(W):
        if mp[i][j] == '
          k += 1
    if k == K:
      rlt += 1
  else:
    if len(l[0]) < H and len(l[1]) < W: 
      for m in [0,1]:
        for n in [0,1]:
          h.append([l[0] + [m],l[1]+[n]])
    elif len(l[0]) == H:
      for n in [0,1]:
        h.append([l[0],l[1]+[n]])
    else:
      for m in [0,1]:
        h.append([l[0]+[m],l[1]])
        
print(rlt)

Solution (Python):
from itertools import product
input = raw_input
h, w, k = map(int, input().split(" "))

mat = [list(input()) for i in range(h)]

n_black = 0
for line in mat:
    for elm in line:
        if elm == "
            n_black += 1

out = 0
for h_pattern in product((False, True), repeat=h):
    for w_pattern in product((False, True), repeat=w):
        
        del_ = 0
        for hi, h_flag in enumerate(h_pattern):
            for wi, w_flag in enumerate(w_pattern):
                if h_flag or w_flag:
                    if mat[hi][wi] == "
                        del_ += 1
                        
        nokori = n_black - del_
        
        if k == nokori:
            out += 1

print(out)

Solution (Python):
import itertools

h, w, k = map(int, input().split())
S = [input() for s in range(h)]
ans = 0
for rows in itertools.product([0, 1], repeat=h):
    for cols in itertools.product([0, 1], repeat=w):
        tmp = 0
        for idx_row, i in enumerate(rows):
            if i == 1:
                continue
            for idx_col, j in enumerate(cols):
                if j == 1:
                    continue
                if S[idx_row][idx_col] == '
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)

Solution (Python):

import sys

sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)










def run():
    H, W, K = list(map(int, sysread().split()))
    C = []
    for i in range(H):
        C.append(input())
    ans = 0
    for i in range(0, 2 ** H):
        for j in range(0, 2 ** W):
            ret = 0
            selected = []
            for l in range(W):
                if not (j >> l) & 1:
                    selected.append(l)
            for k in range(H):
                if not (i >> k) & 1 :
                    for v in selected:
                        if C[k][v] == '
            if ret == K:
                ans += 1
    print(ans)


if __name__ == "__main__":
    run()

Solution (Python):
import numpy as np
from copy import deepcopy
ans = 0
h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]
c = np.array(c)
c = (c == '
for i in range(2 ** (h + w)):
    d = deepcopy(c)
    i = bin(i)
    i = "0" * (h + w - len(i) + 2) + i[2:]
    for j in range(h + w):
        if i[j] == "1" and j < h:
            d[j] = 0
        elif i[j] == "1":
            d[:,j - h] = 0
    if np.sum(d) == k:
        ans += 1
print(ans)

Solution (Python):
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    H, W, K = map(int, input().split())
    matrix = []
    for _ in range(H):
        c = list(input())
        matrix.append(c)
    ans = 0

    for row in range(2**H):
        for col in range(2**W):
            countK = 0
            for h in range(H):
                for w in range(W):
                    if matrix[h][w] == "
                        if (row >> h)&1 and (col >> w)&1:
                            countK += 1
            if countK == K:
                ans += 1
    print(ans)



if __name__ == '__main__':
    solve()

Solution (Python):
h, w, tar = [int(i) for i in input().split()]

line = []
for i in range(h):
    a = input()
    line.append([k for k in a])

ans = 0


import itertools
hs = []
for i in range(h + 1):
    hs.extend(list(itertools.combinations(range(h), i)))

ws = []
for i in range(w + 1):
    ws.extend(list(itertools.combinations(range(w), i)))

for i in hs:
    for j in ws:
        res = 0
        for k in range(h):
            for l in range(w):
                if line[k][l] == "
                    res += 1
        if res == tar:
            ans += 1


print(ans)

Solution (Python):
import copy


def main():
    height, width, leave_black = [int(x) for x in input().split()]
    table = [list(input()) for _ in range(height)]
    ans = 0
    for num_h in range(2 ** height):
        for num_w in range(2 ** width):
            tmp = copy.deepcopy(table)
            for bit_h in range(height):
                if num_h >> bit_h & 1:
                    tmp[bit_h] = ['r'] * width
            for bit_w in range(width):
                if num_w >> bit_w & 1:
                    for row in tmp:
                        row[bit_w] = 'r'
            
            if sum(c == '
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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

from itertools import product

ans = 0
for col, row in product(list(range(2**h)), list(range(2**w))):
    col = f"{int(str(bin(col))[2:]):0{h}}"
    row = f"{int(str(bin(row))[2:]):0{w}}"
    _c = []
    for i, is_col in enumerate(col):
        if int(is_col):
            _c.append(c[i])
    new_c = []
    for j, is_row in enumerate(row):
        if int(is_row):
            cur_c_c = []
            for _c_c in _c:
                cur_c_c.append(_c_c[j])
            new_c.append(cur_c_c)
    if sum([el.count("
        ans += 1



print(ans)

Solution (Python):
import itertools

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

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

ph = list(itertools.product([0,1], repeat=h))
pw = list(itertools.product([0,1], repeat=w))

c = 0
ans = 0
for i in ph:
	for j in pw:
		for m in range(h):
			for n in range(w):
				if d[m][n]=='
					c += 1
		if c == k:
			ans += 1
		c = 0

print(ans)

Solution (Python):


from itertools import product
H, W, K = map(int, input().split())
CC = [list(input()) for _ in range(H)]

C = []

for i in range(H):
    a = []
    for j in range(W):
        if CC[i][j] == '.':
            a.append(0)
        else:
            a.append(1)
    C.append(a)
ret = 0
for ph in product([0,1], repeat=H):
    for pw in product([0,1], repeat=W):
        cnt = 0
        for i in range(len(ph)):
            if ph[i] == 0:
                for j in range(len(C[i])):
                    if C[i][j] == 1 and pw[j] == 0:
                        cnt += 1
        if cnt == K: ret += 1

print(ret)

Solution (Python):

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

import copy
ans =[0]*(h*w+1)
for i in range(2**h):
    for j in range(2**w):
        
        cc = copy.deepcopy(c)
        bi = bin(i)[2:].zfill(h)
        bj = bin(j)[2:].zfill(w)
        for ii in range(h):
            for jj in range(w):
                if bi[ii]=="1":
                    cc[ii]=[2]*w
                if bj[jj]=="1":
                    for kk in range(h):
                        cc[kk][jj]=2
                    
        n_black = sum(ccc.count("
        

        ans[n_black]+=1
print(ans[k])

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline
H,W,K= map(int,input().split())
C = [input().strip() for i in range(H)]
C = [list(map(lambda x : 0 if x == '.' else 1, c)) for c in C]

m = lambda x : 0 if x == '0' else 1
ans = 0
for h in range(2**H):
    for w in range(2**W):
        hb = list(bin(h)[2:])
        hb = [0]*(H-len(hb))+hb
        hp = list( i for i,x in enumerate(hb) if x == '1')
        wb = list(bin(w)[2:])
        wb = [0]*(W-len(wb))+wb
        wp = list( i for i,x in enumerate(wb) if x == '1')
        k = 0
        for i in range(H):
            for j in range(W):
                if i in hp:
                    continue
                if j in wp:
                    continue
                k += C[i][j]
        if k == K:
            ans += 1
print(ans)

Solution (Python):
import itertools

def main():
    H,W,K=map(int,input().split())
    c=[input() for _ in range(H)]
    h=[x for x in range(H)]
    w=[x for x in range(W)]
    ans=0
    for i in range(H):
        for j in range(W):
            for ph in itertools.combinations(h, i):
                for pw in itertools.combinations(w, j):
                    cnt=0
                    for k in range(H):
                        if k in ph: continue
                        for l in range(W):
                            if l in pw: continue
                            if c[k][l]=='
                    if cnt==K: ans+=1
    print(ans)
    return

if __name__=='__main__':
    main()

Solution (Python):
H, W, K = map(int, input().split())
C = [[True if c == "


def width_mask():
    ret_mask = [0] * W
    for i in range(2 ** W):
        for j in range(W):
            ret_mask[j] = (i & 1)
            i >>= 1
        yield ret_mask


def height_mask():
    ret_mask = [0] * H
    for i in range(2 ** H):
        for j in range(H):
            ret_mask[j] = (i & 1)
            i >>= 1
        yield ret_mask


ans = 0

for w_mask in width_mask():
    for h_mask in height_mask():
        count = 0
        for i in range(H):
            for j in range(W):
                if w_mask[j] == 1 and h_mask[i] == 1 and C[i][j]:
                    count += 1

        if count == K:
            ans += 1

print(ans)

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

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

ans = 0
for i in range(2 ** h):
  for j in range(2 ** w):
    bin_i = bin(i).replace('0b','').zfill(h)
    bin_j = bin(j).replace('0b','').zfill(w)
    
    count = 0
    for k in range(h):
      for l in range(w):
        if c[k][l] == '
          count += 1
          
    if K == count:
      ans += 1
          
print(ans)

Solution (Python):
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
import copy

h,w,k=nm()

field = []
for y in range(h):
  field.append([_ for _ in input()])

ans=0

s = set()

for yi in range(2**h):
  f1 = copy.deepcopy(field)
  for yj in range(h):
    if ((yi >> yj) & 1):
      f1[yj] = ['*']*w
    for xi in range(2**w):
      f2= copy.deepcopy(f1)
      for xj in range(w):
        if((xi >> xj) & 1):
          for y in range(h):
            f2[y][xj] = '*'
      
      cnt=0
      for y in range(h):
        for x in range(w):
          if f2[y][x] == '
            cnt+=1

      if cnt==k:
        ans+=1
        s.add(str(f2))

print(len(s))

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

arr = [list(input()) for _ in range(H)]

ans = 0
for row in range(2**H):
  for col in range(2**W):
    count = 0
    for i in range(H):
      if not ((row >> i) & 1): continue
      for j in range(W):
        if not ((col >> j) & 1): continue
        if arr[i][j] == '
          count += 1
    if count == K:
      ans += 1
print(ans)

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


def main():
    h, w, k = map(int, input().split())
    base_table = []
    for i in range(h):
        s = input()
        tmp = []
        for j in s:
            if j == '.':
                tmp.append(0)
            else:
                tmp.append(1)
        base_table.append(tmp)

    tate = [[-1]]
    for n in range(1, h + 1):
        for item in combinations(range(h), n):
            tate.append(list(item))
    yoko = [[-1]]
    for n in range(1, w + 1):
        for item in combinations(range(w), n):
            yoko.append(list(item))

    ans = 0
    for i in tate:
        for j in yoko:
            table = deepcopy(base_table)

            if i[0] != -1:
                for i_idx in i:
                    for s in range(w):
                        table[i_idx][s] = 0
            if j[0] != -1:
                for j_idx in j:
                    for t in range(h):
                        table[t][j_idx] = 0

            cnt = np.array(table).sum()
            if cnt == k:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
h,w,k=map(int,input().split())
c=[input() for i in range(h)]
x=[c[i].count('
y=[]
s=sum(x)
ans=0
for i in range(w):
    count=0
    for j in range(h):
        count+=(c[j][i]=='
    y.append(count)
for i in range(2**(h+w)):
    i='0'*(h+w-len(bin(i)[2:]))+bin(i)[2:]
    count=0
    for j in range(h):
        if i[j]=='1':
            count+=x[j]
    for l in range(w):
        if i[l+h]=='1':
            count+=y[l]
    for j in range(h):
        for l in range(w):
            if i[j]=='1' and i[h+l]=='1':
                if c[j][l]=='
                    count-=1
    if s-count==k:
        ans+=1
print(ans)

Solution (Python):
import math
import collections
import fractions
import itertools
import functools
import operator

def solve():
    h, w, k = map(int, input().split())
    masu = [list(input()) for i in range(h)]
    ans = 0
    for i in range(w+1):
        for k1 in itertools.combinations(range(w), i):
            for j in range(h+1):
                for k2 in itertools.combinations(range(h), j):
                    sushi = 0
                    for y in k2:
                        for x in k1:
                            if masu[y][x] == "
                                sushi += 1
                    if sushi == k:
                        ans += 1
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):

import itertools

H, W, K = map(int, input().split())
grid = [[''] * W for _ in range(H)]
for i in range(H):
    grid[i] = list(str(input()))

ans = 0
for i in itertools.product((0, 1), repeat=H):
    for j in itertools.product((0,1), repeat=W):
        tmp = 0
        for hi, h in enumerate(i):
            for wj, w in enumerate(j):
                if h == 1 and w == 1 and grid[hi][wj] == '
                    tmp += 1
        if tmp == K:
            ans += 1
print(ans)

Solution (Python):
h, w, k = map(int, input().split())
m = [input() for _ in range(h)]
crows = [line.count('
ccols = [0] * w
for j in range(w):
    for i in range(h):
        ccols[j] += (m[i][j] == '
sharps = sum(crows)

from itertools import combinations
if sharps < k:
    print(0)
else:
    ans = 0
    for hi in range(2**h):
        for wi in range(2**w):
            combs = sharps
            remh = []
            for hj in range(h):
                if (hi>>hj)&1:
                    remh.append(hj)
                    combs -= crows[hj]
            remw = []
            for wj in range(w):
                if (wi>>wj)&1:
                    remw.append(wj)
                    combs -= ccols[wj]
            
            for hh in remh:
                for ww in remw:
                    if m[hh][ww] == '
                        combs += 1
            
            if combs == k:
                ans += 1
    print(ans)

Solution (Python):
import itertools
H,W,K=map(int,input().split())
c=[list(input()) for _ in range(H)]
hll=list(itertools.product(range(2),repeat=H))
wll=list(itertools.product(range(2),repeat=W))
ans=0
for hl in hll:
    for wl in wll:
        tc=[]
        for i in c:
            tc.append(i[:])
        for i in range(H):
            if hl[i]==1:
                for j in range(W):
                    tc[i][j]='.'
        for i in range(W):
            if wl[i]==1:
                for j in range(H):
                    tc[j][i]='.'
        t=0
        for i in range(H):
            for j in range(W):
                if tc[i][j]=='
                    t+=1
        if t==K:
            ans+=1
print(ans)

Solution (Python):
import copy
h,w,k = map(int,input().split())
grid = [list(input()) for i in range(h)]

ans = 0
for i in range(2**h):
    for j in range(2**w):
        cnt = 0
        t = copy.deepcopy(grid)
        a = i
        b = j
        while a:
            if a&1:
                for l in range(w):
                    t[cnt][l] = "."
            a = a >> 1
            cnt += 1
        cnt = 0
        while b:
            
            if b&1:
                
                for l in range(h):
                    t[l][cnt] = "."
            b = b >> 1
            cnt += 1
        cnt = 0
        for l in t:
            cnt += l.count("
        if cnt == k:
            ans += 1
            
        
        
print(ans)

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

c = [[] for _ in range(h)]

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

ans = 0
for mask_y in range(1 << h):
    for mask_x in range(1 << w):
        cnt = 0
        for y in range(h):
            for x in range(w):
                if c[y][x] == "
                    cnt += 1
                    if (mask_y >> y) % 2 == 1 or (mask_x >> x) % 2 == 1:
                        cnt -= 1
        if cnt == k:
            ans += 1

print(ans)

Solution (Python):
import sys
import heapq, functools, collections, itertools
import math, random
from collections import Counter, defaultdict






def solve(grid,k):  
    console(grid)
    grid = [[1 if x == "
    console("----- solving ------")
    console(grid)

    res = 0

    for arr in itertools.product([0,1], repeat=len(grid)+len(grid[0])):
        cnt = 0
        for i,row in enumerate(grid):
            for j,cell in enumerate(row):
                if arr[i] == 0 and arr[-j-1] == 0 and cell == 1:
                    cnt += 1
        if cnt == k:
            res += 1
        
    
    return res


def console(*args):  
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return


for case_num in [1]:
    
    

    
    
    
    
    

    
    nrows,_,k = list(map(int,input().split()))

    
    
    
    grid = []
    for _ in range(nrows):
        grid.append(input())

    res = solve(grid,k)  
    
    
    

    
    print(res)

Solution (Python):


def LI():return list(map(int,input().split()))





import itertools
nums = [0,1]

h,w,k=LI()
c=[]
for _ in range(h):
    c.append(list(input()))

f=0
for i in range(h):
    for j in range(w):
        if c[i][j]=="
            f+=1


ans=0
for ii in list(itertools.product(nums,repeat=h)):
    for jj in list(itertools.product(nums,repeat=w)):
        
        cnt=0
        for i,ci in enumerate(ii):
            for j,cj in enumerate(jj):
                if ci==1 or cj==1:
                    if c[i][j]=="
                        cnt+=1
        if cnt==f-k:
            
            ans+=1
                
        
print(ans)

Solution (Python):
H,W,K=map(int,input().split())
F=[input() for _ in range(H)]
ans=0
for i in range(2**H):
  for j in range(2**W):
    cnt=0
    for ii in range(H):
      for jj in range(W):
        if (i>>ii)%2==0 or (j>>jj)%2==0 or F[ii][jj]==".":
          continue
        cnt+=1
    if cnt==K:
      ans+=1
print(ans)