Problem:
 Score : 300 points    Problem Statement We have a grid of H rows and W columns of squares. The color of the square at the i -th row from the top and the j -th column from the left (1 \leq i \leq H, 1 \leq j \leq W) is given to you as a character c_{i,j} : the square is white if c_{i,j} is . , and black if c_{i,j} is # .  Consider doing the following operation:   Choose some number of rows (possibly zero), and some number of columns (possibly zero). Then, paint red all squares in the chosen rows and all squares in the chosen columns.   You are given a positive integer K . How many choices of rows and columns result in exactly K black squares remaining after the operation? Here, we consider two choices different when there is a row or column chosen in only one of those choices.      Constraints  1 \leq H, W \leq 6  1 \leq K \leq HW  c_{i,j} is . or # .         Input Input is given from Standard Input in the following format:  H  W  K  c_{1,1}c_{1,2}...c_{1,W}  c_{2,1}c_{2,2}...c_{2,W}  :  c_{H,1}c_{H,2}...c_{H,W}       Output Print an integer representing the number of choices of rows and columns satisfying the condition.        Sample Input 1 2 3 2
..#
###      Sample Output 1 5  Five choices below satisfy the condition.   The 1 -st row and 1 -st column  The 1 -st row and 2 -nd column  The 1 -st row and 3 -rd column  The 1 -st and 2 -nd column  The 3 -rd column        Sample Input 2 2 3 4
..#
###      Sample Output 2 1  One choice, which is choosing nothing, satisfies the condition.       Sample Input 3 2 2 3
##
##      Sample Output 3 0       Sample Input 4 6 6 8
..##..
.#..#.
#....#
######
#....#
#....#      Sample Output 4 208

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W,K=mi()
    C = [[""]*H for _ in range(W)]
    for h in range(H):
        t = list(input())
        for w in range(W):
            C[w][h] = t[w]
    
    WL = []
    for i in range(2**W):
        w_l = set()
        for j in range(W): 
            if ((i >> j) & 1):
                w_l.add(j)
        WL.append(w_l)

    HL = []
    for i in range(2**H):
        h_l = set()
        for j in range(H): 
            if ((i >> j) & 1):
                h_l.add(j)
        HL.append(h_l)


    def count(graph):
        cnt = 0
        for h in range(H):
            for w in range(W):
                if graph[w][h] == "
                    cnt += 1

        return cnt

    def refill_and_count(wl,hl):
        newC = [[""]*H for _ in range(W)]
        for h in range(H):
            for w in range(W):
                if w in wl or h in hl:
                    newC[w][h] = "r"
                else:
                    newC[w][h] = C[w][h]

        
        return count(newC)

    ans = 0
    for wl in WL:
        for hl in HL:
            
            black = refill_and_count(wl,hl)
            
            if black == K:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

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


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


def dump_dummy(*objects):
    pass


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

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

Solution (Python):


import itertools
import numpy as np

def main():
    H, W, K = tuple(int(c) for c in input().split())
    C = np.zeros((H,W))
    for h in range(H):
        line = input()
        for w in range(len(line)):
            if line[w]=='
                C[h,w] = 1
    
    ans = 0
    for p_h in itertools.product([True,False], repeat=H):
        for p_w in itertools.product([True,False], repeat=W):
            C_t = C.copy()
            C_t[p_h, :] = 0
            C_t[:, p_w] = 0
            if C_t.sum() == K:
                
                ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False



def main():
    H, W, K = MI()
    graph = [None] * H
    black_cnt = 0
    dic = defaultdict(int)
    ans = 0

    for i in range(H):
        s = S()
        graph[i] = s

        for j in range(len(s)):
            if s[j] == '
                dic[(i, j)] += 1
                black_cnt += 1

    N = H + W
    for i in range(2 ** N):
        row = []
        col = []
        for j in range(N):
            if ((i >> j) & 1):
                if j < H:
                    row.append(j)
                else:
                    col.append(j - H)

        current_cnt = black_cnt
        visited = defaultdict(int)
        for i in row:
            for j in range(W):
                visited[(i, j)] += 1
                if (i,j) in dic:
                    current_cnt -= 1

        for i in range(H):
            for j in col:
                if (i,j) in visited:
                    continue
                visited[(i, j)] += 1
                if (i,j) in dic:
                    current_cnt -= 1

        if current_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)]

import itertools

ans = 0
for i in itertools.product([0, 1], repeat=H):
    for j in itertools.product([0, 1], repeat=W):
        count = 0
        for h in range(H):
            for w in range(W):
                if i[h] != 1 and j[w] != 1 and C[h][w] == "
                    count += 1
        if count == K:
            ans += 1
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
c = [list(input().strip()) for _ in range(H)]
b = 0
for y in range(H):
    for x in range(W):
        if c[y][x] == "
            b += 1

ans = 0
for row in range(2 ** H):
    rows = []
    for h in range(H):
        if row & (1 << h):
            rows.append(h)
    for col in range(2 ** W):
        rc = {}
        cols = []
        for w in range(W):
            if col & (1 << w):
                cols.append(w)

        for y in rows:
            for x in range(W):
                rc[(y, x)] = c[y][x]
        for x in cols:
            for y in range(H):
                rc[(y, x)] = c[y][x]

        tb = b
        for v in rc.values():
            if v == "
                tb -= 1
        if tb == K:
            ans += 1
print(ans)

Solution (Python):
H,W,K=map(int, input().split())
A=[]
for i in range(H):
  a=input()
  A.append(a)
  
import itertools
B=list(itertools.product([0,1], repeat=H))
C=list(itertools.product([0,1], repeat=W))
ans=0
for b in B:
  for c in C:
    cnt=0
    for i in range(H):
      for j in range(W):
        if A[i][j]=='
          cnt+=1
    if cnt==K:
      ans+=1
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

def solve():
    H, W, K = map(int, readline().split())
    C = [[1 if c == '

    def f(v, h):
        brd = [list(C[i]) for i in range(H)]
        i = 0
        while v > 0:
            if v & 1:
                for j in range(W):
                    brd[i][j] = 0
            v >>= 1
            i += 1
        
        j = 0
        while h > 0:
            if h & 1:
                for i in range(H):
                    brd[i][j] = 0
            h >>= 1
            j += 1
        
        ret = sum(sum(row) for row in brd)
        return ret

    ans = 0
    for v in range(2 ** H):
        for h in range(2 ** W):
            if f(v, h) == K:
                ans += 1
    
    print(ans)


solve()

Solution (Python):
H, W, K = map(int, input().split())
c = []
for i in range(H):
  tmp = input()
  c.append(tmp)
ans = 0
for h in range(2**H):
  h_list = []
  for i in range(H):
    if ((h >> i) & 1):
      h_list.append(i)
  for w in range(2**W):
    w_list = []
    for j in range(W):
      if ((w >> j) & 1):
        w_list.append(j)
    tmp = 0
    for i in range(H):
      for j in range(W):
        if i in h_list:
          continue
        if j in w_list:
          continue
        if c[i][j] == '
          tmp += 1
    if tmp == K:
      ans += 1
print(ans)

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

init_B=0
for i in range(h):
    cnt = l[i].count('
    init_B+=cnt

from itertools import *

ans=0
for hs in product([True,False], repeat=h):
    for ws in product([True,False], repeat=w):

        cnt=0
        for i in range(h):
            tmp = hs[i]
            if tmp: 
                cnt += l[i].count("
        for j in range(w):
            tmp = ws[j]
            if tmp: 
                for i in range(h):
                    if l[i][j] == "
                        cnt+=1

        if (init_B-cnt)==k:
            ans+=1
print(ans)

Solution (Python):
from itertools import product

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

ans = 0
for selection in product([True, False], repeat=H + W):
    row_sel = selection[:H]
    col_sel = selection[H:]
    count = 0
    for i, j in product(range(H), range(W)):
        if C[i][j] == "
            count += 1
    if count == K:
        ans += 1

print(ans)

Solution (Python):


from copy import deepcopy


def main():
    global ans
    H, W, K = map(int, input().split())
    c = [None] * H
    for i in range(H):
        c[i] = [1 if x == "

    ans = 0

    def rec(i, j, c_, H, W, K):
        global ans

        c_1 = deepcopy(c_)
        c_2 = deepcopy(c_)

        if i < H:
            c_1[i] = [0] * W
            rec(i+1, j, c_1, H, W, K)
            rec(i+1, j, c_2, H, W, K)
        elif j < W:
            for h in range(H):
                c_1[h][j] = 0
            rec(i, j+1, c_1, H, W, K)
            rec(i, j+1, c_2, H, W, K)
        else:
            if sum([sum(row) for row in c_]) == K:
                ans += 1

    rec(0, 0, c, H, W, K)

    return ans


print(main())

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

h, w, k = list(map(int, input().split()))
ss = []
for i in range(h):
    s = input()
    s = s.replace("
    s = list(map(int, list(s)))
    ss.append(s)
ss = np.array(ss)


c = 0
for bih in product([0, 1], repeat = h):
    s = ss.copy()
    s[np.array(bih) == 1] = 0
    for biw in product([0, 1], repeat = w):
        sss = s.copy()
        sss[:, np.array(biw) == 1] = 0
        if np.sum(sss) == k:
            c += 1

print(c)

Solution (Python):
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction

sys.setrecursionlimit(int(pow(10,6)))


mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]



t=1

for _ in range(t):
    H,W,K=L()
    r=[[]]
    for i in range(H):
        x=[]
        for ele in r:
            x.append(ele+[i])
        r+=x
    c=[[]]
    for i in range(0,W):
        x=[]
        for ele in c:
            x.append(ele+[i])
        c+=x

    A=[input() for i in range(H)]
    count=0
    for rows in r:
        for columns in c:
            indiv=0
            for i in range(H):
                for j in range(W):
                    if i not in rows and j not in columns and A[i][j]=="
                        indiv+=1
            if indiv==K:
                
                
                
                count+=1
    print(count)

Solution (Python):
import itertools
import copy
from collections import deque
import heapq
h,w,k = map(int,input().split())
c = [list(input()) for i in range(h)]

ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        ans_check = 0
        h_c = {}
        w_c = {}
        for check in range(h):
            if ((i >> check) & 1):
                h_c[check] = 0
        for check in range(w):
            if ((j >> check) & 1):
                w_c[check] = 0
        
        for hc,n in enumerate(c):
            if not hc in h_c:
                continue
            for wc,m in enumerate(n):
                if not wc in w_c:
                    continue
                if m == "
                    ans_check += 1
        
        if ans_check == k:
            ans += 1
print(ans)

Solution (Python):
from itertools import product
import numpy as np
h,w,k = map(int,input().split())
c = np.array([[*input()] for _ in range(h)])
c = np.where(c=="

all_black = c.sum()
ans = 0
for row in product((0,1), repeat = h):
    for col in product((0,1), repeat = w):
        row = np.array(row)
        col = np.array(col)
        if (c * col).sum() + (c.T * row).sum() - ((c*col).T * row).sum() + k == all_black:
            ans += 1

print(ans)

Solution (Python):
def main():
    H, W, K = map(int, input().split())
    C = [input() for _ in range(H)]
    zenbu = 0
    for h in range(H):
        for w in range(W):
            if C[h][w] == '
                zenbu += 1
    
    if K > zenbu:
        print(0)
        exit()
    ans = 0
    for h in range(2 ** H):
        yoko = []
        for i in range(H):
            if ((h >> i) & 1):
                yoko.append(i)

        for w  in range(2 ** W):
            tate = []

            for j in range(W):
                if (w >> j) & 1:
                    tate.append(j)
            tmp = 0
            for k in range(H):
                for l in range(W):
                    if k in yoko:
                        continue
                    if l in tate:
                        continue
                    if C[k][l] == '
                        tmp += 1
            if tmp == K:
                ans += 1

    print(ans)
        




if __name__ == "__main__":
    main()

Solution (Python):
import itertools
H,W,K = map(int,input().split())
V = [list(input()) for i in range(H)]
ans = 0
for i in list(itertools.product(range(2), repeat=H)):
  for j in list(itertools.product(range(2), repeat=W)):
    temp = 0
    for k in range(H):
      for l in range(W):
        if V[k][l] == '
          if i[k] == 1:
            if j[l] == 1:
              temp += 1
    if temp == K:
      ans += 1
print(ans)

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

s1 = [bin(x)[2:].zfill(h) for x in range(2**h)]
s2 = [bin(x)[2:].zfill(w) for x in range(2**w)]
ans=0
for i in s1:
    for j in s2:
        ans1=0
        for x in range(h):
            for y in range(w):
                if i[x]!='0' and j[y]!='0' and c[x][y]=='
                    ans1+=1
        if ans1==k:
            ans+=1
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
c = [list(input()) for _ in range(H)]
erabikata = 0
for i in range(2 ** H):
    if i == 0:
        continue
    ans_h = []
    for ii in range(H):
        if i >> ii & 1:
            ans_h.append(c[ii])
    if ans_h:
        ans_h = [list(x) for x in zip(*ans_h)]
    for j in range(2 ** W):
        ans_all = []
        count = 0
        if j == 0:
            continue
        for jj in range(W):
            if j >> jj & 1:
                ans_all.append(ans_h[jj])
        for v in sum(ans_all, []):
            if v == '
                count += 1
        if count == K:
            erabikata += 1
print(erabikata)

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

res = 0
for h_flags in range(1 << h):
    for w_flags in range(1 << w):
        black_cnt = 0

        for i in range(h):
            if (h_flags >> i) & 1 == 0:
                continue

            for j in range(w):
                if (w_flags >> j) & 1 == 0:
                    continue

                black_cnt += cells[i][j] == '

        if black_cnt == k:
            res += 1

print(res)

Solution (Python):
from copy import deepcopy

h, w, k = map(int, input().split())
c = [[0] * w for _ in range(h)]
for i in range(h):
    for j, x in enumerate(input()):
        c[i][j] = int(x == "

ans = 0
n = h+w
for bit in range(2**n):
    cc = deepcopy(c)
    for i in range(n):
        if (bit >> i) & 1:
            x = i
            if x >= h: 
                x -= h
                for j in range(h):
                    cc[j][x] = 0
            else:
                for j in range(w):
                    cc[x][j] = 0
    s = sum(map(sum, cc))
    if s == k: ans += 1

print(ans)

Solution (Python):
def main():

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

    c = []
    for _ in range(H):
        c.append(list(input()))
    


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

    b_rows = dict()
    for i in range(H):
        cnt = 0
        for j in range(W):
            if c[i][j] == '
                cnt += 1
        b_rows[i] = cnt

    b_cols = dict()
    for j in range(W):
        cnt = 0
        for i in range(H):
            if c[i][j] == '
                cnt += 1
        b_cols[j] = cnt

    cols = [[]]
    for i in range(W):
        tmp = []
        for v in cols:
            tmp.append(v + [0])
            tmp.append(v + [1])
        cols = tmp

    rows = [[]]
    for i in range(H):
        tmp = []
        for v in rows:
            tmp.append(v + [0])
            tmp.append(v + [1])
        rows = tmp

    ans = 0
    for rw in rows:
        for cl in cols:
            cnt = 0
            for i in range(H):
                if rw[i] == 1: cnt += b_rows[i]
            for j in range(W):
                if cl[j] == 1: cnt += b_cols[j]
            for i in range(H):
                for j in range(W):
                    if rw[i] == 1 and cl[j] == 1 and c[i][j] == '
                        cnt -= 1
            if tot - cnt == K:
                
                ans += 1
    return ans




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

Solution (Python):
import sys
import itertools
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    H, W, K = in_nn()
    c = [list(in_s()) for _ in range(H)]

    comb_h = list(itertools.product([0, 1], repeat=H))
    comb_w = list(itertools.product([0, 1], repeat=W))

    ans = 0
    for ch in comb_h:
        for cw in comb_w:
            tc = copy.deepcopy(c)
            for y, f in enumerate(ch):
                if f:
                    for x in range(W):
                        tc[y][x] = 'a'
            for x, f in enumerate(cw):
                if f:
                    for y in range(H):
                        tc[y][x] = 'a'

            count = 0
            for y in range(H):
                for x in range(W):
                    if tc[y][x] == '
                        count += 1

            if count == K:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W, K = LI()
    c = [list(SS()) for _ in range(H)]

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

    print(ans)
                        



if __name__ == '__main__':
    resolve()

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

import itertools

PRD = list(itertools.product([0,1], repeat=H+W))
ans=0

for i in range(len(PRD)):
    p=PRD[i]
    point=0
    for s in range(H):
        for t in range(W):
            if p[s]+p[H+t]==0 and C[s][t]=='
                point+=1
    if point==K:
        
        ans+=1

print(ans)

Solution (Python):
import itertools

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

m=[input() for i in range(h)]


ans=0
for i in itertools.product([0,1],repeat=h):
    for j in itertools.product([0,1],repeat=w):
        nij=0
        for a in range(h):
            for b in range(w):
                if i[a]!=1 and j[b]!=1 and m[a][b]=="
                    nij+=1
        if nij==k:
            ans+=1

print(ans)

Solution (Python):
from itertools import product
from copy import deepcopy
def solve():
    H,W,K = map(int,input().split())
    c = []
    for _ in range(H):
        c.append(list(input()))
    
    h_combs = list(product([0,1], repeat=H))
    w_combs = list(product([0,1], repeat=W))

    ans = 0
    for h_comb in h_combs:
        for w_comb in w_combs:
            mod_c = deepcopy(c)
            for i in range(H):
                if not h_comb[i]:
                    continue
                for j in range(W):
                    mod_c[i][j] = '.'

            for i in range(W):
                if not w_comb[i]:
                    continue
                for j in range(H):
                    mod_c[j][i] = '.'
            
            cnt = 0
            for h in range(H):
                for w in range(W):
                    if mod_c[h][w] == '
                        cnt += 1
            
            if cnt == K:
                ans += 1
    print(ans)

if __name__ == '__main__':
    solve()

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


def get_turn(num):
    ans = [0]*(H+W)
    for ind in range(H+W):
        if num % 2 == 0:
            ans[ind] = 1
        num //= 2
    return ans

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

times = pow(2, H+W)
ans = 0
for i in range(times):
    turn = get_turn(i)
    if K == get_color(turn):
        ans += 1

print(ans)

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

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




ans=0



for i in range(2**h):
    y=[]
    for j in range(h):
        if (i>>j)&1:
            y.append(j)
       
    for k in range(2**w):
        x=[]
        for l in range(w):
            if (k>>l)&1:
                x.append(l)
        tmp=0
        
        for yy in range(h):
            for xx in range(w):
                if yy not in y and xx not in x:
                    
                    if c[yy][xx]=="
                        tmp+=1
        if tmp==KK:
            ans+=1

print(ans)

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

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

matrix = []
for _ in range(h):
  matrix.append([1 if word=='

h_list = list(range(h))
w_list = list(range(w))

h_check_list = []
w_check_list = []
for i in range(h):
  h_check_list += list(combinations(h_list, i))
for i in range(w):
  w_check_list += list(combinations(w_list, i))

for h_paint in h_check_list:
  for w_paint in w_check_list:
    tmp = np.array(matrix.copy())
    for row in h_paint:
      tmp[row] = [0]*w
    for column in w_paint:
      for i in range(h):
        tmp[i][column] = 0
    if np.sum(tmp)==k:
      cnt+=1
print(cnt)

Solution (Python):
from copy import deepcopy

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

ans = 0
for hh in range(1 << h):
    cp = deepcopy(c)
    for hi in range(6):
        if hh >> hi & 1:
            for wi in range(w):
                cp[hi][wi] = "x"

    for ww in range(1 << w):
        cp2 = deepcopy(cp)
        for wi in range(6):
            if ww >> wi & 1:
                for hi in range(h):
                    cp2[hi][wi] = "x"

        cnt = 0
        for hi in range(h):
            for wi in range(w):
                if cp2[hi][wi] == "
                    cnt += 1

        if cnt == k:
            ans += 1

print(ans)

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

h,w,k = map(int,input().split())
F = []
for i in range(h):
  F.append(list(input()))
  
ans = 0
for hs in product([0,1],repeat=h):
  for ws in product([0,1],repeat=w):
    A = np.array(deepcopy(F))
    for i in range(h):
      if hs[i]:
        A[i,:] = '.'
    for j in range(w):
      if ws[j]:
        A[:,j] = '.'
    if np.sum(A=='
      ans += 1
      
print(ans)

Solution (Python):
h,w,K=map(int,input().split())
s=[list(input())for i in range(h)]
import numpy as np
s=np.array(s)
l=[]

for i in range(h):
    l.append(len(s[i][s[i]=="
for i in range(w):
    l.append(len(s[:,i][s[:,i]=="
ss=sum(l)//2
n=h+w
ans=0
for i in range(1<<n):
    tmp=ss
    for j in range(h):
        if i>>j&1:
            tmp-=l[j]
    for j in range(h,n):
        if i>>j&1:
            tmp-=l[j]
            for idx,k in enumerate(s[:,j-h]):
                if k=="
                    if i>>idx&1:
                        tmp+=1
    if tmp==K:
        ans+=1
print(ans)

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

pos = []

def checkPoints(x,y):
  global pos
  xlist = [x%2, (x//2)%2, (x//4)%2, (x//8)%2, (x//16)%2, (x//32)%2]
  ylist = [y%2, (y//2)%2, (y//4)%2, (y//8)%2, (y//16)%2, (y//32)%2]
  result = 0
  for val in pos:
    if(xlist[val[0]]==0 and ylist[val[1]]==0):
      result += 1
  return result


for y in range(H):
  temp = input()
  for x in range(W):
    if(temp[x]=="
      pos.append([x,y])

allPoints = 0

for y in range(2 ** H):
  for x in range(2 ** W):
    if(checkPoints(x, y) == K):
      allPoints += 1

print(allPoints)

Solution (Python):
import itertools
h,w,k=map(int,input().split())
c = [input() for i in range(h)]
row = []
column = []

for i in range(h):
    cnt = 0
    for g in range(w):
        if c[i][g] == "
            cnt+=1
    row.append(cnt)

for i in range(w):
    cnt = 0
    for g in range(h):
        if c[g][i] == "
            cnt+=1
    column.append(cnt)

ans=0
s = sum(row)

it = list(itertools.product([0,1], repeat=h+w))
for l in it:
    cnt = s
    cnth = []
    cntw = []
    for i in range(h):
        if l[i]==1:
            cnth.append(i)
            cnt -= row[i]
    for g in range(w):
        if l[h+g]==1:
            cntw.append(g)
            cnt -= column[g]
    for i in cnth:
        for g in cntw:
            if c[i][g]=="
                cnt += 1
    if cnt == k:
        ans+=1
print(ans)

Solution (Python):
from itertools import product
import copy

h,w,k = map(int, input().split())
cl = []
b_cnt = 0
for _ in range(h):
    row = list(input())
    cl.append(row)
    b_cnt += row.count('



pattern = 2


ite = product(range(pattern),repeat=h+w)
ans = 0

for it in ite:
    curr_it = list(it)
    it_h = curr_it[:h]
    it_w = curr_it[h:]



    curr_cl = copy.deepcopy(cl)
    cnt = 0
    for hi in range(h):
        if it_h[hi] == 0: continue
        for wi in range(w):
            if curr_cl[hi][wi] == '
                curr_cl[hi][wi] = 'r'
                cnt += 1
    for wi in range(w):
        if it_w[wi] == 0: continue
        for hi in range(h):
            if curr_cl[hi][wi] == '
                curr_cl[hi][wi] = 'r'
                cnt += 1

    if b_cnt-cnt == k:
        ans += 1
    
    
    
    

print(ans)

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

ans = 0
from itertools import product
for i in product([0,1], repeat=h):
    for j in product([0,1], repeat=w):
        num = 0
        for a in range(h):
            for b in range(w):
                if g[a][b] == '
                    num += 1
        if num == k:
            ans += 1

print(ans)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

H,W,K=LI()
MP=[input() for i in range(H)]

res = 0
for bits in range(1 << (H+W)):
    k = 0
    for i in range(H):
        for j in range(W):
            if not (((bits >> i) & 1) or ((bits >> H+j) & 1)):
                k += (MP[i][j] == "
    res += (k == K)

print(res)