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 math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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 power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w,k = lr()
a = [input() for i in range(h)]
ans = 0
for i in range(2**(h+w)):
    tmp = [[a[q][l] for l in range(w)] for q in range(h)]
    for j in range(h+w):
        if (j < h and ((i >> j) & 1)):
            for q in range(w):
                tmp[j][q] = '0'
        elif (j >= h and ((i >> j) & 1)):
            for q in range(h):
                tmp[q][j-h] = '0'
    pre = 0
    for q in range(h):
        for l in range(w):
            if tmp[q][l] == '
                pre+=1
    if pre == k:
        ans+=1
print(ans)

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

ans = 0
for i in range(h):
    maze[i] = input()

import itertools
ans=0
count=0
for casei in itertools.product([0,1], repeat=h):
    for casej in itertools.product([0,1], repeat=w):
        for i in range(h):
            for j in range(w):
                if maze[i][j]=='
                    count+=1
        if count == k:
            ans+=1
        count=0

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq


def solve(H, W, K, field):
    
    N = 2 ** (H + W)
    F = "{:0" + str(H + W) + "b}"
    ans = 0
    for n in range(N):
        HM = F.format(n)[:H]
        WM = F.format(n)[H:]
        c = 0
        for h in range(H):
            for w in range(W):
                if HM[h] == "1":
                    continue
                if WM[w] == "1":
                    continue
                if field[h][w] == "
                    c += 1
        if c == K:
            ans += 1

    return ans




if __name__ == "__main__":
    H, W, K = tuple(map(int, input().split(" ")))
    field = [input() for _ in range(H)]
    print(solve(H, W, K, field))

Solution (Python):


def count_kuro(c, bit_i, bit_j):
    list_i = []
    for i in range(H):
        if bit_i>>i&1:
            list_i.append(i)
    list_j = []
    for j in range(W):
        if bit_j>>j&1:
            list_j.append(j)

    tansaku = [
        (i,j) for i in range(H) for j in range(W)
        if i in list_i and j in list_j
    ]

    return sum([c[dot[0]][dot[1]]=='


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

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

count = 0
for bit_i in range(2**H):
    for bit_j in range(2**W):
        num_kuro = count_kuro(c, bit_i, bit_j)
        if num_kuro == K:
            count+=1

print(count)

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

c = [list(input()) for i in range(H)]

ans = 0
for bity in product([True, False], repeat=H):
    for bitx in product([True, False], repeat=W):
        area = [[0] * W for i in range(H)]
        for i in range(H):
            for j in range(W):
                area[i][j] = c[i][j]
        
        
        for y in range(H):
            if bity[y]:
                for x in range(W):
                    area[y][x] = '.'
        for x in range(W):
            if bitx[x]:
                for y in range(H):
                    area[y][x] = '.'
        temp = sum([a.count('
        if temp == K:
            ans+=1
print(ans)

Solution (Python):
from collections import *
h,w,K = map(int,input().split())
a = []
for i in range(h):
	a.append(list(input()))
ans = 0
for i in range(1 << h):
	for j in range(1 << w):
		c = [[a[J][I] for I in range(w)] for J in range(h)]
		for k in range(h):
			if(i&(1 << k)):
				for kk in range(w):
					c[k][kk] = 'R'
		for k in range(w):
			if(j&(1 << k)):
				for kk in range(h):
					c[kk][k] = 'R'
		ct = 0
		for k in range(h):
			ct += c[k].count('
		if(ct == K):
			ans += 1
print(ans)

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy


MOD = 10 ** 9 + 7




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

for a in range(1<<h):
    for b in range(1<<w):
        M = [[0] * w for _ in range(h)]
        for i in range(h):
            for j in range(w):
                if A[i][j] == "
                    M[i][j] = 1
        for i in range(h):
            if (a >> i) & 1:
                for j in range(w):
                    M[i][j] = 0

        for j in range(w):
            if (b >> j) & 1:
                for i in range(h):
                    M[i][j] = 0

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

        if count == k:
            ans += 1

print(ans)

Solution (Python):
from itertools import product

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

count=0
for x in product((0,1),repeat=h):
    for y in product((0,1),repeat=w):
        sm=0
        for i in range(h):
            if x[i]==0 : continue
            for j in range(w):
                if y[j]==0 : continue
                if lst[i][j]=="
        if sm==k : count+=1

print(count)

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

ans=0

for i in range(2**H):
    cc=deepcopy(c)
    for b in range(H):
        if (i>>b)&1==1:
            for k in range(W):
                cc[b][k]='r'

    for j in range(2**W):
        ccc=deepcopy(cc)
        for b in range(W):
            if (j>>b)&1==1:
                for k in range(H):
                    ccc[k][b]='r'
        cnt=0
        for i in range(H):
            for j in range(W):
                if ccc[i][j]=='
                    cnt+=1
        
        if cnt==K:
            ans+=1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import copy
H,W,K = map(int,input().split())
C_org = [list(input().rstrip()) for _ in range (H)]
ans = 0 
def change(C, k, row):
    if row==0:
        for i in range(W):
            C[k][i] = '.'
    else:
        for i in range(H):
            C[i][k] = '.'
    return 

for i in range(1<<H):
    C1 = copy.deepcopy(C_org)
    for k in range(H):
        if i==0:
            break
        if i&1:
            for t in range(W):
                C1[k][t] = '.'
        i>>=1

    for j in range(1<<W):
        C2 = copy.deepcopy(C1)
        for k in range(W):
            if j==0:
                break
            if j&1:
                for t in range(H):
                    C2[t][k] = '.'
            j>>=1
        
        cnt = 0
        for cc in C2:
            for c in cc:
                if c=='
                    cnt += 1
        if cnt==K:
            ans += 1
print(ans)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

h,w,k = inm()
c = []
for i in range(h):
    c.append(ins())
ans = 0
for i in range(2**h):
    for j in range(2**w):
        sm = 0
        for x in range(h):
            for y in range(w):
                if (i>>x)%2>0 and (j>>y)%2>0 and c[x][y]=='
                    sm += 1
        if sm==k:
            ans += 1
print(ans)

Solution (Python):
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W, K = map(int, readline().split())
    G = [readline() for _ in range(H)]

    
    
    

    

    ans = 0
    for rh in range(1, H + 1):
        for combh in combinations(range(H), rh):
            for rw in range(1, W + 1):
                for combw in combinations(range(W), rw):
                    tmp = 0
                    for i in combh:
                        for j in combw:
                            if G[i][j] == '
                                tmp += 1
                    if tmp == K:
                        ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):


import sys
stdin = sys.stdin
from itertools import product

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def f(c, hi, wi):
    cnt = 0
    for i, hb in enumerate(hi):
        if hb == 0:
            continue
        for j, wb in enumerate(wi):
            if wb == 0:
                continue
            if c[i][j] == 1:
                cnt += 1
    return cnt



def main():
    h, w, k = na()
    hb = list(product([0,1], repeat=h))
    wb = list(product([0,1], repeat=w))
    c = list()
    for _ in range(h):
        c += [[1 if s == "
    
    cnt = 0
    for hi in hb:
        for wi in wb:
            if f(c, hi, wi) == k:
                cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

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

cmat=[[x=="." for x in input()] for _ in range(H)]


answer=0
for perm in itertools.product([True,False],repeat=H+W):
  
  row_set=set()
  for i in range(H):
    if perm[i]:
      row_set.add(i)
  
  col_set=set()
  for i in range(H,H+W):
    if perm[i]:
      col_set.add(i-H)      
  
  
  cnt=0
  for i in range(H):
    for j in range(W):
      if not cmat[i][j] and not i in row_set and not j in col_set:
        cnt+=1
        
  if cnt==K:
    answer+=1
    
print(answer)

Solution (Python):
H, W, K = map(int, input().split())
c = [input() for _ in range(H)]
ans = 0
for i in range(2 ** H):
    for j in range(2 ** W):
        tmp = 0
        for h in range(H):
            if i & (1 << h):
                continue
            for w in range(W):
                if j & (1 << w):
                    continue
                if c[h][w] == "
                    tmp += 1
        if tmp == 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(2**H):
    for j in range(2**W):
        mm = 0
        for h in range(H):
            for w in range(W):
                if ((i>>h)&1) and ((j>>w)&1) and C[h][w]=="
                    mm += 1
        if mm==K:
            ans += 1
            
print(ans)

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)



import itertools




h,w,k=n1()
s=s4(h)
H=list(itertools.product([0,1],repeat=h))
W=list(itertools.product([0,1],repeat=w))

ans=0
for tate in H:
    for yoko in W:
        c=0
        for i in range(h):
            for j in range(w):
                if tate[i] == 1 or yoko[j] == 1:
                    pass
                elif s[i][j]=="
                    c+=1
        if c==k:
            ans+=1
print(ans)

Solution (Python):
import itertools

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

ans = 0
for hh in itertools.product("01", repeat = h):
    h_lst = []
    for i, s in enumerate(hh):
        if s == "1":
            h_lst.append(i)
    for ww in itertools.product("01", repeat = w):
        w_lst = []
        for i, s in enumerate(ww):
            if s == "1":
                w_lst.append(i)
        tmp = 0            
        for i in h_lst:
            for j in w_lst:
                if c[i][j] == "
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)

Solution (Python):
import sys
from itertools import product

import numpy as np

input = sys.stdin.readline


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

    ans = 0
    for h_comb in product((True, False), repeat=H):
        for w_comb in product((True, False), repeat=W):
            grid = np.array(c, dtype=np.int64)
            for i, paint in enumerate(h_comb):
                if paint:
                    grid[i, :] = 0
            for i, paint in enumerate(w_comb):
                if paint:
                    grid[:, i] = 0
            if np.sum(grid) == 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):
    dh = [(i >> j) & 1 for j in range(h)]
    for k in range(2**w):
        dw = [(k >> j) & 1 for j in range(w)]
        res = 0
        for nh in range(h):
            for nw in range(w):
                if dh[nh]==0 and dw[nw]==0:
                    if c[nh][nw]=="
                        res += 1
        if res == K: 
            ans += 1

print(ans)

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

field = [input() for _ in range(h)]


ans = 0
for bit_h in range(2**h):
    for bit_w in range(2**w):
        count = 0
        use_h = []
        for i in range(h):
            if (bit_h >> i) & 1:
                use_h.append(field[i])

        for j in range(w):
            if (bit_w >> j) & 1:
                for line in use_h:
                    if line[j] == "
                        count += 1

        if count == k:
            ans += 1

print(ans)

Solution (Python):


def oneBit(bitarr,k):
    return (bitarr & 1 << k) > 0


def main():
    H,W,K = map(int,input().split())
    C = [list(input())for i in range(H)]
    hMax = 2**H
    wMax = 2**W
    c=0
    for h in range(hMax):
        for w in range(wMax):
            bc = 0
            for y in range(H):
                for x in range(W):
                    if C[y][x] == "
                        bc +=1
            if bc == K:
                c += 1
    print(c)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product
H,W,K = map(int, input().split())
C = []
for _ in range(H):
  C.append(input())
  
ans = 0
for hp in product([0,1], repeat=H):
  for wp in product([0,1], repeat=W):
    wk = 0
    for i in range(H):
      for j in range(W):
        if C[i][j] == '
          wk += 1
    
    if wk == K:
      ans += 1
      
print(ans)

Solution (Python):
h,w,K=map(int,input().split())
c=[input() for i in range(h)]
ans=0
for i in range(2**h):
    for j in range(2**w):
        d=[[c[z][v] for v in range(w)]for z in range(h)]
        for k in range(h):
            if (i>>k)&1:
                for l in range(w):
                    d[k][l]="x"
        for k in range(w):
            if (j>>k)&1:
                for l in range(h):
                    d[l][k]="x"
        cnt=0
        for k in range(h):
            for l in range(w):
                cnt+=(d[k][l]=="
        ans+=(cnt==K)
print(ans)

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

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    c = [SI() for _ in range(H)]
    ans = 0
    for i in range(2**H):
        for j in range(2**W):
            cnt = 0
            for a in range(H):
                if (1 << a) & i:
                    for b in range(W):
                        if (1<<b) & j:
                            cnt += (c[a][b] == "

            if cnt == K: ans+= 1
    print (ans)



if __name__ == '__main__':
    main()

Solution (Python):
from copy import deepcopy

R, C, K = [int(x) for x in input().split()]

gridOriginal = [list(input()) for r in range(R)]

initBlack = 0
for r in range(R):
    for c in range(C):
        if gridOriginal[r][c] == "
            initBlack += 1

count = 0
for rowMask in range(1 << R):
    for colMask in range(1 << C):
        grid = deepcopy(gridOriginal)
        removed = 0
        for r in range(R):
            for c in range(C):
                if grid[r][c] == "
                    removed += 1
                    grid[r][c] = "R"

        if initBlack - removed == K:
            count += 1

print(count)

Solution (Python):
h,w,k = map(int,input().split())
grid = [list(input())for i in range(h)]
from copy import deepcopy
maze = deepcopy(grid)
ans = 0
for i in range(2**h):
    for j in range(2**w):
        point = 0
        for bh in range(h):
            if ((i>>bh)&1):
                for a in range(w):
                    grid[bh][a] = '0'
        for bw in range(w):
            if ((j >> bw)&1):
                for b in range(h):
                    grid[b][bw] = '0'
        for ii in range(h):
            for jj in range(w):
                if grid[ii][jj] == '
                    point += 1
        
        if point == k:
            ans += 1
        
        grid = deepcopy(maze)
print(ans)

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

def int2bit(n, l):
	bit = [0 for i in range(l)]
	i = 0
	while n > 0:
		bit[i] = n % 2
		n = n // 2
		i += 1
	return bit

ans = 0
for h in range(2**H):
	ph = int2bit(h, H)
	for w in range(2**W):
		pw = int2bit(w, W)
		paint = [[(ph[i] == 1 or pw[j] == 1) for j in range(W)] for i in range(H)]
		cnt = 0
		for i in range(H):
			for j in range(W):
				if not paint[i][j] and G[i][j] == "
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)

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

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

B = [input().rstrip() for _ in range(H)]


def get_black(X, Y):
    ret = 0
    for i in range(W):
        for j in range(H):
            if i in X or j in Y: continue
            if B[j][i] == '
    return ret

ans = 0

for i in range(1 << W):
    for j in range(1 << H):
        X = set()
        Y = set()
        for x in range(W):
            if (1 << x) & i: X.add(x)
        for y in range(H):
            if (1 << y) & j: Y.add(y)

        if get_black(X, Y) == K:
            ans += 1
print(ans)

Solution (Python):
import copy

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
ans=0
boards=[]
for i in range(2**h):
  tmp=copy.deepcopy(board)
  bit1=format(i,'b')
  bit1='0'*(h-len(bit1))+bit1
  for th in range(h):
    if bit1[th]=='0':
      continue
    for tw in range(w):
      tmp[th][tw]='.'
  boards.append(tmp)
for i in range(len(boards)):
  for j in range(2**w):
    tmp=copy.deepcopy(boards[i])
    bit2=format(j,'b')
    bit2='0'*(w-len(bit2))+bit2
    for tw in range(w):
      if bit2[tw]=='0':
        continue
      for th in range(h):
        tmp[th][tw]='.'
    cnt=0
    for th in range(h):
      for tw in range(w):
        if tmp[th][tw]=='
          cnt+=1
    if cnt==k:
      ans+=1
print(ans)

Solution (Python):
import copy

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

    ans = 0
    for i in range(1 << h):
        c1 = copy.deepcopy(c)
        x = i
        p = 0
        while x > 0:
            if x & 1 == 1:
                c1[p] = ['x'] * w
            x = x >> 1
            p += 1
        for j in range(1 << w):
            c2 = copy.deepcopy(c1)
            x = j
            p = 0
            while x > 0:
                if x & 1 == 1:
                    for l in range(h):
                        c2[l][p] = 'x'
                x = x >> 1
                p += 1
            count = 0
            for l in range(h):
                for m in range(w):
                    if c2[l][m] == '
                        count += 1
            if count == k:
                ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
h,w,k=map(int,input().split())
C=[[0]*w for i in range(h)]
for i in range(h):
    c=input()
    for j in range(w):
        if c[j]=="
            C[i][j]=1

ans=0
for i in range(2**h):
    for j in range(2**w):
        R=[]
        for p in range(h):
            if i>>p&1:
                R.append([1]*w)
            else:
                R.append([0]*w)
        for q in range(w):
            if j>>q&1:
                for p in range(h):
                    R[p][q]=1
        cnt=0
        for p in range(h):
            for q in range(w):
                if C[p][q]==1 and R[p][q]==0:
                    cnt+=1
        if cnt==k:
            ans+=1
print(ans)

Solution (Python):
h,w,x = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for i in range(2**(h+w)):
    tnp = 0
    bad = []
    for j in range(h+w):
        if ((i>>j)&1):
            bad.append(j)
    for j in range(h):
        for k in range(w):
            if (c[j][k]=="
                if (j in bad or k+h in bad):
                    continue
                else:
                    tnp += 1
    if (tnp == x):
        ans += 1
print(ans)

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    H,W,K=mis()
    c = [input() for _ in range(H)]
    ans = 0
    for D in product((0, 1), repeat=H+W):
        h = D[:H]
        w = D[H:]
        if sum(c[y][x]=='
            ans += 1
    print(ans)






main()

Solution (Python):
import itertools

h, w, k = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for x, y in itertools.product(range(2 ** h), range(2 ** w)):
    cnt = 0
    for i in range(h):
        for j in range(w):
            if x >> i & 1 or  y >> j & 1: continue
            if c[i][j] == '
    if cnt == k:
        ans += 1
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

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

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

r_bit = 1 << H
w_bit = 1 << W



ans = 0
for r in range(r_bit):
    n_row = []
    for i in range(H):
        if r & 1:
            n_row.append(i)
        r >>= 1

    for c in range(w_bit):
        

        n_col = []

        for j in range(W):
            if c & 1:
                n_col.append(j)
            c >>= 1

        cnt = 0
        for i in range(H):
            for j in range(W):
                if i in n_row or j in n_col:
                    continue
                if C[i][j] == "
                    cnt += 1

        if cnt == K:
            ans += 1

print(ans)

Solution (Python):
import copy

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

c = [list(input()) for i in range(H)]

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

ans = 0

for i in range(2**H):
    d = copy.deepcopy(c)
    for j in range(H):
        if 2**j & i > 0:
            for k in range(W):
                d[j][k] = "."
    for j in range(2**W):
        e = copy.deepcopy(d)
        for k in range(W):
            if 2**k & j > 0:
                for l in range(H):
                    e[l][k] = "."
        
        if count(e)==K:
            ans += 1

print(ans)

Solution (Python):
from itertools import product
H,W,K = map(int,input().split())
C = [input().strip() for _ in range(H)]
ans = 0
for row in product((0,1),repeat=H):
    for col in product((0,1),repeat=W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if row[i]==0 and col[j]==0 and C[i][j]=="
                    cnt += 1
        if cnt==K:
            ans += 1
print(ans)

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

ans = 0
for h in range(1 << H):
    for w in range(1 << W):
        black = 0
        for i in range(H):
            for j in range(W):
                if ((h >> i) & 1) + ((w >> j) & 1) == 0:  
                    black += (c[i][j] == '
        if black == K:
            ans += 1

print(ans)

Solution (Python):















mod = int(1e9+7)

INF = 1<<50

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

def main():
    h,w,k = readInt()
    c = []
    for i in range(h):
        c.append(input())
    ans = 0
    for i in range(1<<h):
        for j in range(1<<w):
            res = 0
            for l in range(h):
                if (i>>l)&1:
                    for m in range(w):
                        if (j>>m)&1:
                            if c[l][m]=='
                                res += 1
            if res==k:
                ans += 1
    print(ans)
    return

if __name__=='__main__':
    main()

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

c = []

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

	c.append(d)

result = 0

for m1 in range(1 << h):
	for m2 in range(1 << w):			
		d = []
		for i in range(h):
			x = []
			for j in range(w):
				x.append(c[i][j])
			d.append(x)


		for row in range(h):
			if (m1 >> row) % 2 == 1:
				for j in range(w):
					d[row][j] = '.'

		for col in range(w):
			if (m2 >> col) % 2 == 1:
				for i in range(h):
					d[i][col] = '.'

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

		if count == k:
			result += 1

print(result)

Solution (Python):
import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
C = np.array([[0 if c == '.' else 1 for c in input()] for _ in range(H)],
             dtype=int)
ans = 0
for bh in itertools.product([True, False], repeat=H):
    D = C.copy()
    D[np.array(bh), :] = np.zeros(W, dtype=int)
    for bw in itertools.product([True, False], repeat=W):
        E = D.copy().T
        E[np.array(bw), :] = np.zeros(H, dtype=int)
        if np.sum(E) == K:
            ans += 1
print(ans)