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
import time
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(hl, wl):
  cnt = 0
  for h in range(H):
    if h in hl:
      continue
    for w in range(W):
      if w in wl:
        continue
      if grid[h][w] == "
        cnt += 1
  if cnt == K:
    return True
  else:
    return False

H,W,K = IL()
grid = [list(S()) for i in range(H)]

ans = 0
for i in range(1<<H):
  a = []
  for ii in range(H):
    if (i >> ii) & 1 == 1:
      a.append(ii)
  for j in range(1<<W):
    b = []
    for jj in range(W):
      if (j >> jj) & 1 == 1:
        b.append(jj)
    if tami(a, b):
      ans += 1
print(ans)

Solution (Python):
import numpy as np

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

area = np.zeros([h, w], dtype=int)

for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "
            area[i, j] = 1


ans = 0

for i in range(2**(h+w)):
    area_ = area.copy()

    for j in range(h+w):
        if ((i >> j) & 1):
            if j < h:
                area_[j, :] = 0
            else:
                area_[:, j-h] = 0
    
    if np.sum(area_) == k:
        ans += 1
print(ans)

Solution (Python):
def m():
    H, W, K = map(int, input().split())
    G = [list(input()) for _ in range(H)]
    ans = 0
    for y in range(2 ** H):
        for x in range(2 ** W):
            y_mask = bin(y)[2:].zfill(H)
            x_mask = bin(x)[2:].zfill(W)
            black_cnt = 0
            for j in range(H):
                for i in range(W):
                    if y_mask[j] == '1':
                        continue
                    if x_mask[i] == '1':
                        continue
                    if G[j][i] == '
                        black_cnt += 1
            if black_cnt == K:
                ans += 1
    return ans


print(m())

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

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

ans = 0

for p in range(h):
    h_combs = list(combinations(list(range(h)), p))
    for q in range(w):
        w_combs = list(combinations(list(range(w)), q))
        for h_comb in h_combs:
            for w_comb in w_combs:
                cnt = 0
                for i in range(h):
                    for j in range(w):
                        if i not in h_comb and j not in w_comb and C[i][j] == '
                            cnt += 1
                if cnt == k:
                    ans += 1
print(ans)

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

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

def calc(lst1, lst2):
    tmp = 0
    for h in range(H):
        for w in range(W):
            if G[h][w] == '
                tmp += 1
    
    return tmp



ans = 0
for i in range(2 ** H):
    lst1 = [0] * H
    for j in range(H):
        if (i >> j) & 1:
            lst1[j] = 1
    for k in range(2 ** W):
        lst2 = [0] * W
        for l in range(W):
            if (k >> l) & 1:
                lst2[l] = 1
        if calc(lst1, lst2) == K:
            
            ans += 1

print (ans)

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

input_data = []
for i in range(H):
    input_list = list(input())
    input_data.append(input_list)

input_H_list = []
for i in range(2 ** H):
    para_ = i
    temp_ = []
    for k in range(H):
        if para_ % 2 == 0:
            temp_.append(0)
        else:
            temp_.append(1)
        para_ = para_ // 2
    input_H_list.append(temp_)

input_W_list = []
for i in range(2 ** W):
    para_ = i
    temp_ = []
    for k in range(W):
        if para_ % 2 == 0:
            temp_.append(0)
        else:
            temp_.append(1)
        para_ = para_ // 2
    input_W_list.append(temp_)

ans_count = 0    
    
for H_list in input_H_list:
    for W_list in input_W_list:
        not_black_counter = 0
        for i in range(H):
            if H_list[i] == 1:
                not_black_counter += W
            else:
                
                for j in range(W):
                    if W_list[j] == 1:
                        not_black_counter += 1
                    else:
                        if input_data[i][j] == ".":
                            not_black_counter += 1
        if not_black_counter + K  == H * W:
            ans_count += 1
print(ans_count)

Solution (Python):
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 


h, w, k = map(int, input().split())
s = ['' for _ in range(h)]
ans = 0
for i in range(h):
    s[i] = input()
for xi in range(2**h):
    t = deepcopy(s)
    b = [0 for _ in range(w)]
    for i in range(h):
        if ((xi >> i)&1):
            t[i] = ''
            for j in range(w):
                t[i] += '.'
    for i in range(h):
        for j in range(w):
            if t[i][j] == '
                b[j] += 1
    for xj in range(2**w):
        sumv = 0
        for j in range(w):
            if ((xj >> j)&1):
                sumv += b[j]
        if sumv == k: ans += 1
print(ans)

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

ans = 0
for i in range(2**H):
    i_format = "0"+str(H)+"b"
    i_bin = format(i, i_format)
    for j in range(2**W):
        j_format = "0"+str(W)+"b"
        j_bin = format(j, j_format)
        count = 0
        for n in range(H):
            row = c[n]
            if i_bin[n] == "0":
                for m in range(W):
                    if j_bin[m] == "0":
                        if row[m] == "
                            count += 1      
        if count == K:
            ans += 1
print(ans)

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

ans = 0
for h in range(2**H):
    hbit = bin(h)[2:].zfill(H)
    hselect = set()
    for hi, hb in enumerate(hbit):
        if hb == '1':
            hselect.add(hi)
    for w in range(2**W):
        wbit = bin(w)[2:].zfill(W)
        wselect = set()
        for wi, wb in enumerate(wbit):
            if wb == '1':
                wselect.add(wi)

        tmp = 0
        for i in range(H):
            if i in hselect:
                continue
            for j in range(W):
                if j in wselect:
                    continue
                if S[i][j] == '
                    tmp += 1

        if tmp == K:
            ans += 1

print(ans)

Solution (Python):
h,w,k = map(int,input().split())
raw = []
for _ in range(h):
  tmp = input()
  add = []
  for j in range(w):
    if tmp[j] == '.':
      add.append(0)
    else:
      add.append(1)
  raw.append(add)
ans = 0
time1 = [0 for i in range(h)]
time2 = [0 for j in range(w)]
def nex(time):
  l = len(time)
  for i in range(l):
    if time[i] == 0:
      time[i] = 1
      return time
    else:
      time[i] = 0
  else:
    return 'over'
from copy import deepcopy as dc
while time1 != 'over':
  use = dc(raw)
  for i in range(h):
    if time1[i] == 1:
      for j in range(w):
        use[i][j] = 0
  while time2 != 'over':
    now = dc(use)
    for j in range(w):
      if time2[j] == 1:
        for i in range(h):
          now[i][j] = 0
    cnt = 0
    for i in range(h):
      cnt += sum(now[i])
    
    if cnt == k:
      ans += 1
    time2 = nex(time2)
  time1 = nex(time1)
  time2 = [0 for _ in range(w)]
print(ans)

Solution (Python):
h,w,k = map(int, input().split())
c = [list(input()) for i in range(h)]
d = [[0 if j == "." else 1 for j in i] for i in c]
ans = 0
for i in range(2 ** h):
    a = [0] * h
    for j in range(h):
        if (i >> j) & 1:
            a[j] = 1
    for I in range(2 ** w):
        b = [0] * w
        kuro = 0
        for J in range(w):
            if (I >> J) & 1:
                b[J] = 1
        for k1,v1 in enumerate(d):
            if a[k1]:
                continue
            for k2,v2 in enumerate(v1):
                if b[k2]:
                    continue
                kuro += v2
        if kuro == k:
            ans += 1
print(ans)

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

def cnt(table):
    ret = 0
    for row in range(h):
        for col in range(w):
            ret += (table[row][col] == "
    return ret

ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        c_copy = deepcopy(c)
        for row in range(h):
            if ((i >> row) & 1):
                for col in range(w):
                    c_copy[row][col] = ":"
        for col in range(w):
            if ((j >> col) & 1):
                for row in range(h):
                    c_copy[row][col] = ":"
        ans += (cnt(c_copy) == k)
print(ans)

Solution (Python):
from sys import stdin
from collections import Counter
h,w,k = map(int,stdin.readline().split())
bl = 0
arr = [list(stdin.readline()) for _ in range(h)]
row = Counter()
col = Counter()
for i in range(h):
    for j in range(w):
        if arr[i][j] == '
            bl += 1
            row[i] += 1
            col[j] += 1
ans = 0
for i in range(2**h):
    for j in range(2**w):
        x,y = bin(i)[2:],bin(j)[2:]
        val = bl
        for bit in range(len(x)-1,-1,-1):
            if x[bit] == '1':
                val -= row[len(x)-1-bit]
                for bit1 in range(len(y)-1,-1,-1):
                    if y[bit1] == '1':
                        val += (arr[len(x)-1-bit][len(y)-1-bit1]=='
        for bit in range(len(y)-1,-1,-1):
            if y[bit] == '1':
                val -= col[len(y)-1-bit]
        if val==k:
            ans += 1
print(ans)

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



ans = 0

for hn in range(2**H):
    hbit = bin(hn)[2:].zfill(H)
    for wn in range(2**W):
        wbit = bin(wn)[2:].zfill(W)
        count = 0
        
        for h in range(H):
            for w in range(W):
                if hbit[h] == "1" and wbit[w] == "1" and c[h][w] == "
                    count += 1
        if count == K:
            ans += 1

print(ans)

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

ans = 0
for i in range(2**h):
  for j in range(2**w):
    res = 0
    hlist = []
    wlist = []
    for k in range(h):
      if (i >> k) & 1:
        hlist.append(k)
    for k in range(w):
      if (j >> k) & 1:
        wlist.append(k)
    
    for k in range(h):
      if k in hlist:
        continue
      for l in range(w):
        if l in wlist:
          continue
        if mas[k][l] == "
          res += 1
    if res == v:
      ans += 1
        
print(ans)

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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



lst=list(product(range(2),repeat=H+W))
nlst=set()
a=0
for l in lst:
    _C=copy.deepcopy(C)
    for h in range(H):
        if l[h]:
            for w in range(W):
                _C[h][w]="R"
    for w in range(W):
        if l[H+w]:
            for h in range(H):
                _C[h][w]="R"
    
    if sum([_C[h].count("
    
        s=""
        for h in range(H):
            s+="".join(_C[h])
        if not s in nlst:
            a+=1
            nlst.add(s)
print(a)

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

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

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 ((i >> k) & 1) and ((j >> l) & 1) and C[k][l] == "
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)

Solution (Python):


import copy
import itertools


def solve(h, w, k, stage):
    res = 0
    is_sel_rs = itertools.product((False, True), repeat=h)
    is_sel_cs = itertools.product((False, True), repeat=w)
    for irs, ics in itertools.product(is_sel_rs, is_sel_cs):
        st = copy.deepcopy(stage)
        for r0, ir in enumerate(irs):
            if ir:
                for c in range(w):
                    st[r0][c] = "*"
        for c0, ic in enumerate(ics):
            if ic:
                for r in range(h):
                    st[r][c0] = "*"
        num_blacks = 0
        for r, c in itertools.product(range(h), range(w)):
            if st[r][c] == "
                num_blacks += 1
        if num_blacks == k:
            res += 1
    return res


def main():
    h, w, k = (int(z) for z in input().split())
    stage = [list(input()) for _ in range(h)]
    res = solve(h, w, k, stage)
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import product

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

    tot = 0

    rows = []
    for row in G:
        rows.append((cnt := row.count('
        tot += cnt

    cols = []
    for col in zip(*G):
        cols.append(col.count('

    ans = 0
    for row_conds in product([0, 1], repeat=H):
        t = tot
        for r, row_cond in enumerate(row_conds):
            if row_cond:
                t -= rows[r]
        for col_conds in product([0, 1], repeat=W):
            s = t
            for c, col_cond in enumerate(col_conds):
                if col_cond:
                    s -= cols[c]
                    for r2, row_cond2 in enumerate(row_conds):
                        if row_cond2 and G[r2][c] == '
                            s += 1
            if s == K:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w,K = na()
g = []
for i in range(h):
    g.append(ns())

ans = 0
for i in range(2**h):
    for j in range(2**w):
        a = 0
        for k in range(h):
            for l in range(w):
                if g[k][l] == '
                    a += 1
        if a == K:
            ans += 1

print(ans)

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

ans = 0
for h_mask in product([False, True], repeat=H):
    for w_mask in product([False, True], repeat=W):
        count = 0
        for h in range(H):
            for w in range(W):
                
                if h_mask[h] and w_mask[w] and c[h][w] == "
                    count += 1
        if count == K:
            ans += 1
print(ans)

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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


ans = 0
for i in range(2 ** H):
    row = []
    for j in range(H):
        if ((i >> j) & 1):
            row.append(j)
    for k in range(2 ** W):
        column = []
        for l in range(W):
            if ((k >> l) & 1):
                column.append(l)
        cnt = 0
        for r in row:
            for c in column:
                if cells[r][c] == '
                    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())
ans = 0
for i in range(2**h):
    for j in range(2**w):
        tmp = 0
        for m in range(h):
            for n in range(w):
                if (i >> m) & 1:
                    continue
                if (j >> n) & 1:
                    continue
                if c[m][n] == "
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)

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

area = []
ans = 0
for i in range(h):
    x = list(input())
    area.append(x)

for i in range(2**(h+w)):
    num = format(i, 'b').zfill(h+w)
    cnt = 0
    for j in range(h):
        for l in range(w):
            if num[j] == '1' or num[h+l] == '1':
                continue
            else:
                if area[j][l] == '
                    cnt += 1
    if cnt == k:
        ans += 1

print(ans)

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

black = 0
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            black += 1

if black < K:
    print(0)
else:
    for i in range(1 << H):
        for j in range(1 << W):
            cnt = 0
            watched = [[False for _ in range(W)] for __ in range(H)]
            for h in range(H):
                if 1 << h & i:
                    for w in range(W):
                        if S[h][w] == "
                            cnt += 1
                            watched[h][w] = True

            for w in range(W):
                if 1 << w & j:
                    for h in range(H):
                        if S[h][w] == "
                            cnt += 1
                            watched[h][w] = True

            if black - cnt == K:
                ans += 1

    print(ans)

Solution (Python):
from copy import deepcopy
from itertools import product
H, W, K = map(int, input().split())
ls = []
for i in range(H):
    s = list(input())
    ls.append(s)
ans = 0
for x in product([0, 1], repeat=H):
    for y in product([0, 1], repeat=W):
        p = deepcopy(ls)
        num = 0
        for i, j in enumerate(x):
            if j == 1:
                for w in range(W):
                    p[i][w] = '?'
        for i, j in enumerate(y):
            if j == 1:
                for h in range(H):
                    p[h][i] = '?'
        for k in p:
            for l in k:
                if l == '
                    num += 1
        if num == K:
            ans += 1
print(ans)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,k=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(1<<(h+w)):
    hh=[False]*h
    ww=[False]*w
    for j in range(h+w):
      if i&(1<<j):
        if j<h:
          hh[j]=True
        else:
          ww[j-h]=True

    cnt=0
    for j in range(h):
      if hh[j]:
        continue
      for _k in range(w):
        if ww[_k]:
          continue

        if field[j][_k]=='
          cnt+=1

    if cnt==k:
      ans+=1

  return ans


print(main())

Solution (Python):


from itertools import chain, combinations

def subsets(iterable, low=0, high=None):
    "subsets([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    if high is None:
        high = len(s)
    return chain.from_iterable(combinations(s, r) for r in range(low, high+1))

H, W, K = input().split(' ')

H = int(H)
W = int(W)
K = int(K)

A = []

for _ in range(H):
    row = input()
    A += [row]



ret = 0

def ok(rows, cols, A):
    A = [list(row) for row in A]
    for x in rows:
        for y in range(W):
            A[x][y] = '.'
    for y in cols:
        for x in range(H):
            A[x][y] = '.' 
    
    return K == sum(sum(1 for r in row if r == '

for h in subsets(range(0, H)):
    for w in subsets(range(0, W)):
        if ok(h, w, A):
            ret += 1        
            

print(ret)

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

ans = 0
for i in range(1<<H):
    for j in range(1<<W):
        count = 0
        for h in range(H):
            for w in range(W):
                if ((i&(1<<h)==0) and (j&(1<<w)==0) and C[h][w]=="
                    count += 1
        if(count == K):
            ans += 1
print(ans)

Solution (Python):
import copy

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

ans = 0

for i in range(2**(h+w)):
    m = copy.deepcopy(c)
    for j in range(w):
        if i&(1<<j):
            for x in range(h):
                if m[x][j] == '
                    m[x][j] = 'r'
    for j in range(w, w+h):
        if i&(1<<j):
            for x in range(w):
                if m[j-w][x] == '
                    m[j-w][x] = 'r'
    cur = 0
    for x in range(h):
        for j in range(w):
            if m[x][j] == '
                cur += 1
    if cur == k:
        ans += 1

print(ans)

Solution (Python):
from itertools import product
h, w, k = map(int, input().split())
grid = [input() for _ in range(h)]

a = [i for i in range(h)]
b = [i for i in range(w)]


def cnt(i, j):
    ret = 0
    for k in range(len(i)):
        for t in range(len(j)):
            if i[k] == 0 or j[t] == 0:
                continue
            if grid[k][t] == "
                ret += 1

    return ret

ans = 0
for i in product([0, 1], repeat=h):
    for j in product([0, 1], repeat=w):
        if cnt(i, j) == k:
            ans += 1

print(ans)

Solution (Python):
from itertools import product

import numpy as np


H, W, K = map(int, input().split())
field = np.array([[int(c == "

ans = 0
for hs in product([0, 1], repeat=H):
    for ws in product([0, 1], repeat=W):
        test_field = field.copy()
        for i, h in enumerate(hs):
            if h == 1:
                test_field[i] = 0
        for j, w in enumerate(ws):
            if w == 1:
                test_field[:, j] = 0
        if test_field.sum() == K:
            ans += 1
print(ans)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    H, W, K = LI()
    maze = SR(H)
    ans = 0
    for h in range(H+1):
        for w in range(W+1):
            for painted_row in itertools.combinations(range(H), h):
                for painted_col in itertools.combinations(range(W), w):
                    black = 0
                    for i in range(H):
                        for j in range(W):
                            if (i not in painted_row) and (j not in painted_col) and maze[i][j] == "
                                black += 1
                    if black == K:
                        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()


def main():
    H, W, K = map(int, input().split())
    C = [input() for _ in range(H)]
    ans = 0
    for row in range(1 << H):
        for col in range(1 << W):
            cnt = 0
            for i in range(H):
                for j in range(W):
                    if (row & (1 << i)) or (col & (1 << j)): continue
                    if C[i][j] == '
                        
                        cnt += 1
            
            if cnt == K:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
h,w,k=map(int,input().split())
c=[input() for _ in range(h)]
ans=0
for i in range(2**h):
  sr=set([])
  for hi in range(h):
    if (i>>hi)&1:
      sr.add(hi)
  for j in range(2**w):
    sc=set([])
    for wi in range(w):
      if (j>>wi)&1:
        sc.add(wi)
    cnt=0
    for hi in range(h):
      for wi in range(w):
        if hi not in sr and wi not in sc and c[hi][wi]=='
          cnt+=1
    if cnt==k:
      ans+=1
      
print(ans)

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline



def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    h, w, k = geta(int)
    c = []
    for _ in range(h):
        c.append(gete())

    ans = 0
    for b in range(2**(h+w)):
        ih = []
        iw = []
        for i in range(h):
            ih.append(b & 1 == 1)
            b >>= 1
        for i in range(w):
            iw.append(b & 1 == 1)
            b >>= 1

        rem = 0
        for i in range(h):
            if ih[i]:
                continue
            for j in range(w):
                if iw[j]:
                    continue
                if c[i][j] == "
                    rem += 1

        if rem == k:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def ct(arr,rows,cols):
	ret = 0
	for i in range(len(arr)):
		for j in range(len(arr[0])):
			if(rows[i]=='0' and cols[j]=='0' and arr[i][j]=='
				ret+=1
	return ret
h,w,k = list(map(int,input().split()))
arr = []
for i in range(h):
	l = input()
	arr.append(l)
	
		
ans = 0
for i in range(2**h-1,-1,-1):
	for j in range(2**w-1,-1,-1):
		if ct(arr,(bin(i)[2:]).zfill(h),(bin(j)[2:]).zfill(w))==k:
			ans+=1
print(ans)

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

cnt = 0
for h in range(2**H):
    h_bits = [j for j in range(H) if (h >> j &1)]
    for w in range(2**W):
        w_bits = [j for j in range(W) if (w >> j &1)]
        blacks = 0
        for hi in h_bits:
            for wi in w_bits:
                blacks += 1 if table[hi][wi] == "
        cnt += 1 if blacks == K else 0

print(cnt)

Solution (Python):

import sys
input = sys.stdin.readline

h, w, K = map(int, input().split())
field = []
for _ in range(h):
    line = input().rstrip()
    field.append(line)

ans = 0
for i in range(2**h):
    for j in range(2**w):
        cnt = 0
        for k in range(h):
            if i & (1 << k):
                continue
            for l in range(w):
                if j & (1 << l):
                    continue
                if field[k][l] == "
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Solution (Python):
from itertools import combinations as comb

h,w,k = map(int,input().split())
g = [input() for i in range(h)]

row = [i for i in range(h)]
col = [i for i in range(w)]
ANS = 0

for i in range(h+1):
	for cr in comb(row, i):
		for j in range(w+1):
			for cc in comb(col, j):
				gp = [list(s) for s in g]
				for ligne in cr:
					for colonne in range(w):
						gp[ligne][colonne] ="r"
				for colonne in cc:
					for ligne in range(h):
						gp[ligne][colonne] = "r"
				reste = 0
				for ligne in gp:
					reste+=ligne.count("
				if reste == k:
					ANS+=1
print(ANS)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def gen_comb(n):
    c = []
    for i in range(n):
        for comb in itertools.combinations([j for j in range(n)], i):
            c.append(list(comb))
    return c

def count(C, arr1, arr2):
    n_row = len(C)
    n_col = len(C[0])
    s1 = set(arr1)
    s2 = set(arr2)
    cnt = 0
    for r in range(n_row):
        for c in range(n_col):
            if r in s1:
                continue
            if c in s2:
                continue
            if C[r][c] == '
                cnt += 1
    return cnt

def main():
    H, W, K = LI()
    C = []
    for i in range(H):
        C.append(S())

    h_comb = gen_comb(H)
    w_comb = gen_comb(W)
    cnt = 0
    for ixs in h_comb:
        for jxs in w_comb:
            if count(C, ixs, jxs) == K:
                cnt += 1
    print(cnt)


main()