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

Solution (Python):
h, w, k = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0
for patH in range(0, 2**h):
    for patW in range(0, 2**w):
        cnt = 0
        for y in range(h):
            for x in range(w):
                if patH & 2 ** y or patW & 2 ** x:
                    continue
                elif c[y][x] == '
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Solution (Python):
import copy
h,w,k= map(int, input().split())
gr = [list(input()) for i in range(h)]
ans = 0
for i in range(1<<h):
    for j in range(1<<w):
        grnow = copy.deepcopy(gr)
        for i2 in range(h):
            if(1<<i2) & i:
                grnow[i2]=['*']*w
        for j2 in range(w):
            if(1<<j2) & j:
                for k2 in range(h):
                    grnow[k2][j2]='*'
        cnt = 0
        for i2 in range(h):
            for j2 in range(w):
                if grnow[i2][j2]=='
                    cnt += 1

        if cnt == k:
            ans += 1

print(ans)

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    H,W,K=map(int,input().split())
    mas=[list(input().strip("\n")) for i in range(H)]
    bcnt=0
    for i in range(H):
        bcnt+=mas[i].count("
    ans=0
    for i in range(2**H):
        for j in range(2**W):
            cnt=bcnt
            for x in range(H):
                for y in range(W):
                    if (i>>x&1 or j>>y&1) and mas[x][y]=="
                        cnt-=1
            if cnt==K:
                ans+=1
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Solution (Python):
def resolve():
    import itertools
    h, w, k = map(int, input().split())
    c = [input() for _ in range(h)]
    ans = 0
    for i in itertools.product([True, False], repeat=h):
        for j in itertools.product([True, False], repeat=w):
            black = 0
            for p in range(h):
                for q in range(w):
                    if i[p] and j[q] and c[p][q] == "
                        black += 1
            if black == k:
                ans += 1
    print(ans)


if __name__ == '__main__':
    resolve()

Solution (Python):
h,w,k=map(int,input().split())
c=[input() for i in range(h)]
ans=0
for p in range(2**(h+w)):
    bi=bin(p)[2:].zfill(h+w)
    cnt=0
    for i in range(h):
        for j in range(w):
            if c[i][j]=="
                cnt+=1
    
    if cnt==k: ans+=1
print(ans)

Solution (Python):
h, w, K = map(int, input().split())
c_mat = []
for _ in range(h):
    c_mat.append(input())
ans = 0
for i in range(1<<h):
    for j in range(1<<w):
        res = 0
        for k in range(h):
            if i >> k & 1:
                continue
            for l in range(w):
                if j >> l & 1:
                    continue
                if c_mat[k][l] == '
                    res += 1
        if res == K:
            ans += 1
print(ans)

Solution (Python):
from itertools import product

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

result = 0
for a in product([True, False], repeat=H):
    for b in product([True, False], repeat=W):
        t = 0
        for y in range(H):
            if a[y]:
                continue
            for x in range(W):
                if b[x]:
                    continue
                if c[y][x] == '
                    t += 1
        if t == K:
            result += 1
print(result)

Solution (Python):
import collections
h,c,k = map(int,raw_input().split(' '))
res = 0
mat = [raw_input() for ii in range(h)]
for mii in range(2 ** h):
	for mjj in range(2 ** c):
		count = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if (mii >> i) & 1 == 0 and (mjj >> j) & 1 == 0:
					count += 1 if mat[i][j] == '
		if count == k:
			res += 1
print res

Solution (Python):
import sys
from copy import deepcopy
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

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

maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

ans = 0
for i in range(1<<H):
    for j in range(1<<W):
        res = deepcopy(maze)
        for k in range(H):
            if i>>k&1:
                for l in range(W):
                    res[k][l] = "."
        for k in range(W):
            if j>>k&1:
                for l in range(H):
                    res[l][k] = "."

        ct = 0
        for k in range(H):
            for l in range(W):
                if res[k][l] == "
                    ct += 1
        
        if ct == K:
            ans += 1
            
print(ans)

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

ans = 0
for r in range(1<<h):
    for c in range(1<<w):
        cnt = 0
        for i in range(h):
            for j in range(w):
                if r >> i & 1 and c >> j & 1 and ss[i][j] == '
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Solution (Python):


LI = lambda: list(map(int, input().split()))


H, W, K = LI()
C = [input() for _ in range(H)]


def solve(n1, n2):
    l1 = {i for i in range(H) if (n1 >> i) % 2 == 1}
    l2 = {i for i in range(W) if (n2 >> i) % 2 == 1}
    k = 0
    for i in range(H):
        if i in l1:
            continue
        for j in range(W):
            if j in l2:
                continue
            if C[i][j] == "
                k += 1
    if k == K:
        return 1
    else:
        return 0


def main():
    n1, n2 = 2 ** H, 2 ** W
    ans = 0
    for i in range(n1):
        for j in range(n2):
            ans += solve(i, j)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
h,w,k = map(int,input().split())
c = []
for i in range(h):
    s = input()
    c.append(s)
def dfs(i,a,b):
    if i == h+w:
        count = 0
        for j in range(h):
            if a[j] == 0:
                continue
            for l in range(w):
                if b[l] == 0:
                    continue
                if c[j][l] == '
                    count+=1
        if count == k:
            return 1
        else:
            return 0
    if i<h:
        d = a.copy()
        d[i]+=1
        return dfs(i+1,a,b) + dfs(i+1,d,b)
    else:
        d = b.copy()
        d[i-h]+=1
        return dfs(i+1,a,b) + dfs(i+1,a,d)
tmp1 = [0 for i in range(h)]
tmp2 = [0 for i in range(w)]
print(dfs(0,tmp1,tmp2))

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

cnt = sum(row.count('

ans = 0
for b in range(1<<(H+W)):
    h,w = divmod(b,(1<<W))
    st = set()
    for i in range(H):
        if h&(1<<i):
            for j in range(W):
                if C[i][j] == '
                    st.add((i,j))
    for j in range(W):
        if w&(1<<j):
            for i in range(H):
                if C[i][j] == '
                    st.add((i,j))
    if len(st)==cnt - K:
        ans += 1
print(ans)

Solution (Python):
it = lambda: list(map(int, input().strip().split()))

def paint(G, H, W, a, b):
    ans = 0
    for i in range(H):
        if a & (1 << i):
            for j in range(W):
                if G[i][j] == '
                    ans += 1
    return ans

def solve():
    ans = 0
    H, W, K = it()
    G = [input().strip() for _ in range(H)]
    for a in range(1 << H):
        for b in range(1 << W):
            if paint(G, H, W, a, b) == K:
                ans += 1
    return ans

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

Solution (Python):
import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
c=[]
for i in range(h):
    sub=input().rstrip()
    c.append(sub)


ans=0
for i in range(2**h):
    for j in range(2**w):
        check=[[True]*w for _ in range(h)]
        for l in range(h):
            if (i>>l)%2==1:
                for m in range(w):
                    check[l][m]=False
        for l in range(w):
            if (j>>l)%2==1:
                for m in range(h):
                    check[m][l]=False

        temp=0
        for l in range(h):
            for m in range(w):
                if c[l][m]=='
                    temp+=1

        if temp==k:
            ans+=1

print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    
    

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

    def calc(tate, yoko):
        cnt = 0
        for i in range(h):
            if i in tate:
                continue
            for j in range(w):
                if j in yoko:
                    continue
                if c[i][j] == '
                    cnt += 1
        if cnt == k:
            return True
        else:
            return False


    for i in range(h+1):
        for tate in combinations(range(h), i):
            for j in range(w+1):
                for yoko in combinations(range(w), j):
                    if calc(tate, yoko):
                        res += 1
    
    print(res)


if __name__ == '__main__':
    main()

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

kotae = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        count = 0
        for a in range(h):
            for b in range(w):
                if(table[a][b] == "
                    count += 1

        if(count == k):
            kotae += 1


print(kotae)

Solution (Python):
from itertools import product

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

ans = 0
for a in product([0, 1], repeat=H):
    for b in product([0, 1], repeat=W):
        cnt = 0
        for i in range(H):
            if a[i] == 1:
                continue
            for j in range(W):
                if b[j] == 1:
                    continue
                if grid[i][j] == '
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)

Solution (Python):
import math
import sys
from itertools import permutations


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

ans=0
for i in range(2**H):
    for j in range(2**W):
        count=0
        str1="{0:0"+str(H)+"b}"
        b1=str1.format(i)
        str2="{0:0"+str(W)+"b}"
        b2=str2.format(j)

        for x in range(H):
            for y in range(W):
                if b1[x]=='0' and b2[y]=='0' and arr[x][y]=='
                    count+=1
        if count==K:
            ans+=1
print(ans)

Solution (Python):
from copy import deepcopy
from pprint import pprint
h, w , k = map(int, input().split())
maze = []
res = 0
for _ in range(h):
    l = list(input())
    maze.append(l)
for hpat in range(2**h):
    for wpat in range(2**w):
        dat = deepcopy(maze)
        for hh in range(h):
            if (hpat >> hh) & 1 == 1:
                dat[hh] = ["-"] * w
        for ww in range(w):
            if (wpat >> ww) & 1 == 1:
                for i in range(h):
                    dat[i][ww] = "-"
        
        cnt = 0
        for i in range(h):
            cnt += dat[i].count("
        if cnt == k:
            res += 1
print(res)

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

H, W, K = MAP()
grid = [[]] * H
for i in range(H):
    grid[i] = list(input())

ans = 0
for bit1 in range(1<<H):
    for bit2 in range(1<<W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if grid[i][j] == '
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

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

itr=itertools.product([0,1],repeat=h+w)

ans=0
tar=0
for i in range(h):
    for q in range(w):
        if C[i][q]=="
            tar+=1
tar-=k

for t in itr:
    cnt=0
    for i in range(h):
        for q in range(w):
            if C[i][q]=="
                cnt+=1
    if cnt == tar:
        ans+=1

print(ans)

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

ans = 0

for i in range(2**(H+W)):
    h = set()
    for j in range(H):
        if (i >> j) % 2 == 1:
            h.add(j)
    w = set()
    for j in range(W):
        if (i >> (j + H)) % 2 == 1:
            w.add(j)
    tmp = 0
    for j in range(H):
        if j in h:
            continue
        for k in range(W):
            if k in w:
                continue
            if c[j][k] == '
                tmp += 1

    if tmp == K:
        ans += 1

print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        lower, upper = [], []
        i = 1
        while i * i <= n:
            if n % i == 0:
                lower.append(i)
                if i != n // i:
                    upper.append(n // i)
            i += 1
        return lower + upper[::-1]

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def solve():
    H, W, K = Scanner.map_int()
    S = [[0 for _ in range(W)] for _ in range(H)]
    for h in range(H):
        s = Scanner.string()
        for w in range(W):
            if s[w] == '
                S[h][w] = 1
    ans = 0
    for w in range(1 << W):
        for h in range(1 << H):
            field = copy.deepcopy(S)
            for i in range(W):
                if w >> i & 1:
                    for u in range(H):
                        field[u][i] = 0
            for i in range(H):
                if h >> i & 1:
                    for v in range(W):
                        field[i][v] = 0
            cnt = 0
            for u in range(H):
                for v in range(W):
                    if field[u][v] == 1:
                        cnt += 1
            if cnt == K:
                ans += 1
    print(ans)


def main():
    
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
import copy

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

maze = [0]*h
for i in range(h):
    maze[i] = list(input())
    
ans = 0
for row in range(2**h):
    redr = []
    for maskr in range(h):
        if row&(1<<maskr):
            redr.append(maskr)
    ma = copy.deepcopy(maze)
    for r in redr:
        for i in range(w):
            ma[r][i] = "$"
    for col in range(2**w):
        check = copy.deepcopy(ma)
        redc = []
        for maskc in range(w):
            if col&(1<<maskc):
                redc.append(maskc)
        for c in redc:
            for i in range(h):
                check[i][c] = "$"
        tmp = 0
        for r in range(h):
            for c in range(w):
                if check[r][c] == "
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


from itertools import product
h, w, k = inpl()
data = [list(input()[:-1]) for _ in range(h)]
ans = 0
for t in product([0, 1], repeat=h):
    for s in product([0, 1], repeat=w):
        tmp = 0
        for i in range(h):
            for j in range(w):
                if data[i][j] == "
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)

Solution (Python):
import copy
h,w,k = map(int,input().split())
c = [list(input()) for i in range(h)]
count = 0
for i in range(2**h):
    for j in range(2**w):
        d = copy.deepcopy(c)
        for t in range(h):
            if (i >> t) & 1: 
                for q in range(w):
                    d[t][q] = "x"
        for t in range(w):
            if (j >> t) & 1: 
                for q in range(h):
                    d[q][t] = "x"
        ci = 0
        for m in d:
            ci += m.count("
        if ci == k:
            count += 1

print(count)

Solution (Python):
def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
h,w,k=map(int,input().split())
c=[]
for i in range(h):
  a=input()
  c.append(a)
ans=0
for i in range(2**h):
  iconvert=base10toN(i,2)
  ic=[]
  for _ in range(h-len(iconvert)):
    ic.append('0')
  for _ in range(len(iconvert)):
    ic.append(iconvert[_])
  for j in range(2**w):
    jconvert=base10toN(j,2)
    jc=[]
    for _ in range(w-len(jconvert)):
      jc.append('0')
    for _ in range(len(jconvert)):
      jc.append(jconvert[_])
    count=0
    for a in range(h):
      for b in range(w):
        if ic[a]=='0' and jc[b]=='0' and c[a][b]=='
          count+=1
    if count==k:
      ans+=1
print(ans)

Solution (Python):
H, W, K = map(int,input().split())
c = [[0]*W for i in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        if s[j]=='
            c[i][j] = 1
ans=0
from itertools import product
for i in product([0, 1], repeat = H):
    for j in product([0, 1], repeat =W):
        cnt = 0
        for x in range(H):
            for y in range(W):
                if c[x][y] == 1:
                    if i[x] == 0 and j[y] == 0:
                        cnt+=1
        if cnt == K:
            ans+=1
print(ans)

Solution (Python):
def is_ok(h, w, ptn, c, k):
    cnt = 0

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

    if cnt == k:
        return True
    else:
        return False


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

n = h + w
cnt = 0

for i in range(2 ** n):
    ptn = []
    for j in range(n):
        if ((i >> j) & 1):
            ptn.append(j)
    if is_ok(h, w, ptn, c, k):
        cnt += 1

print(cnt)

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

for i in range(h):
    c = list(input())
    cs.append(c)

ans = 0
for i in range(2**h):
    for j in range(2**w):
        cnt = 0
        for ii in range(h):
            for jj in range(w):
                if ((i >> ii) & 1) and ((j >> jj) & 1) and cs[ii][jj] == "
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Solution (Python):
def main():
    h, w, k = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    ans = now = 0
    for now_h in range(pow(2, h)):
        for now_w in range(pow(2, w)):
            now = 0
            for i in range(h):
                for j in range(w):
                    if (now_h >> i) & 1 or (now_w >> j) & 1:
                        continue
                    elif grid[i][j] == "
                        now += 1
            if now == k:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft



def main():
    h, w, k = map(int, input().split())
    c = [input() for i in range(h)]
    ans = []
    def dfs1(i, a):
        if i == h:
            dfs2(0, [0]*w, a)
            return
        dfs1(i+1, a)
        a[i] = 1
        dfs1(i+1, a)
        a[i] = 0

    def dfs2(i, b, a):
        if i == w:
            cnt = 0
            for i in range(h):
                for j in range(w):
                    if a[i] != 0 and b[j] != 0 and c[i][j] == '
                        cnt += 1
            if cnt == k:
                ans.append(1)
            return
        dfs2(i+1, b, a)
        b[i] = 1
        dfs2(i+1, b, a)
        b[i] = 0

    dfs1(0, [0] * h)
    print(len(ans))
main()

Solution (Python):
from copy import deepcopy
from itertools import product

h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]
a = 0
for y in product((0, 1), repeat=h):
    for x in product((0, 1), repeat=w):
        d = deepcopy(c)
        for row in range(h):
            if y[row] == 1:
                d[row] = ["r"] * w
        for col in range(w):
            if x[col] == 1:
                for row in range(h):
                    d[row][col] = "r"
        a += sum(row.count("
print(a)

Solution (Python):
def examA():
    N = I()
    ans = (10000 - N)%1000
    print(ans)
    return

def examB():
    T = ["AC","WA","TLE","RE"]
    N = I()
    S = [SI()for _ in range(N)]

    ans = [0]*4
    for s in S:
        for i in range(4):
            if s==T[i]:
                ans[i] += 1
                break
    for i in range(4):
        print(T[i]+" x "+str(ans[i]))
    return

def examC():
    H, W, K = LI()
    C = [[""]*W for _ in range(H)]
    for h in range(H):
        S = SI()
        for w in range(W):
            C[h][w] = S[w]
    ans = 0
    
    for hi in range(1<<H):
        nowC = deepcopy(C)
        for h in range(H):
            if hi&(1<<h):
                for i in range(W):
                    nowC[h][i] = "R"
        for wi in range(1 << W):
            nowCC = deepcopy(nowC)
            for w in range(W):
                if wi & (1 << w):
                    for i in range(H):
                        nowCC[i][w] = "R"
            cnt = 0
            for h in range(H):
                for w in range(W):
                    if nowCC[h][w] == "
                        cnt += 1
            if cnt == K:
                
                ans += 1
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29


DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    H,W,K = isRaw()
    cs = [sRaw() for i in range(H)]
    ans =0
    for hc in range(0,2**H):
        for wc in range(0,2**W):
            n= 0
            for h in range(H):
                for w in range(W):
                    if (hc&(1<<h)!=0) and (wc&(1<<w)!=0) and cs[h][w]=="
                        n+=1
            if n==K:
                ans+=1
    print(ans)
main()

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    C = [input().strip("\n") for _ in range(H)]
    ans = 0
    rh = [True] * H
    rw = [True] * W
    for h in range(2 ** H):
        hh = h
        for i in range(H):
            if hh % 2 == 1: rh[i] = False
            else: rh[i] = True
            hh //= 2
        for w in range(2 ** W):
            ww = w
            for j in range(W):
                if ww % 2 == 1: rw[j] = False
                else: rw[j] = True
                ww //= 2
            
            count = 0
            for sh in range(H):
                for sw in range(W):
                    if rh[sh] and rw[sw] and C[sh][sw] == "
            if count == K: ans += 1
    print(ans)


    return 0

if __name__ == "__main__":
    solve()

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

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

C = np.zeros((H, W))
for i in range(H):
    S = input()
    for j, s in enumerate(S):
        if s == '
            C[i, j] = 1
ans = 0
for h in range(H):
    for i in combinations(range(H), h):
        for w in range(W):
            for j in combinations(range(W), w):
                C_ = C.copy()
                for a in i:
                    C_[a, :] = 0
                for b in j:
                    C_[:, b] = 0
                if np.sum(C_) == K:
                    ans += 1
print(ans)