AtCoder Beginner Contest 173 - H and V

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-----
2 3 2
..#
###

-----Sample Output-----
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

Source: atcoder | Difficulty: EASY


Solutions:
(h, w, k) = map(int, input().split())
ans = [list(input()) for i in range(h)]
n = h + w
answer = 0
for i in range(1 << n):
	cond = [0] * n
	for j in range(n):
		if 1 & i >> j:
			cond[j] = 1
	count = 0
	for i in range(h):
		for j in range(w):
			if cond[i] == 0 and cond[h + j] == 0 and (ans[i][j] == '#'):
				count += 1
	if count == k:
		answer += 1
print(answer)


(h, w, k) = map(int, input().split())
X = [[1 if a == '#' else 0 for a in input()] for _ in range(h)]
ans = 0
for ii in range(1 << h):
	for jj in range(1 << w):
		if sum([sum([X[i][j] for j in range(w) if jj >> j & 1]) for i in range(h) if ii >> i & 1]) == k:
			ans += 1
print(ans)


(h, *c) = open(0)
(h, w, k) = map(int, h.split())
print(sum((k == sum((y >> w >> z // w & y % 2 ** w >> z % w & 1 and '.' > c[z // w][z % w] for z in range(h * w))) for y in range(1 << h + w))))


(H, W, K) = map(int, input().split())
c = [list(input()) for _ in range(H)]
ans = 0
for maskR in range(1 << H):
	for maskC in range(1 << W):
		blk = 0
		for i in range(H):
			for j in range(W):
				if maskR >> i & 1 == 0 and maskC >> j & 1 == 0 and (c[i][j] == '#'):
					blk += 1
		if blk == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
A = []
ans = 0
black = 0
for i in range(H):
	A.append(list(input()))
for i in range(1 << H):
	for j in range(1 << W):
		black = 0
		for m in range(H):
			for n in range(W):
				if A[m][n] == '#' and i >> m & 1 and j >> n & 1:
					black += 1
		if black == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = []
for _ in range(H):
	c.append(input())
ans = 0
for h in range(2 ** H):
	for w in range(2 ** W):
		b = 0
		for i in range(H):
			for j in range(W):
				if h >> i & 1 == 0 and w >> j & 1 == 0:
					if c[i][j] == '#':
						b += 1
		if b == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for bi in range(1 << h):
	for bj in range(1 << w):
		tmp = sum((c[i][j] == '#' for i in range(h) for j in range(w) if bi >> i & 1 and bj >> j & 1))
		if tmp == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [list(input()) for i in range(h)]
a = 0
for i in range(1 << h + w):
	x = 0
	for j in range(h):
		for l in range(w):
			if i >> j & 1 and i >> l + h & 1:
				if c[j][l] == '#':
					x += 1
	if x == k:
		a += 1
print(a)


(H, W, K) = map(int, input().split())
c = [input() for i in range(H)]
ans = 0
for h in range(1 << H):
	for w in range(1 << W):
		count = 0
		for i in range(H):
			for j in range(W):
				if h >> i & 1 and w >> j & 1:
					if c[i][j] == '#':
						count += 1
		if count == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
C = [input() for i in range(H)]
t = 0
for h in range(2 ** H):
	for w in range(2 ** W):
		b = 0
		for i in range(H):
			if h & 2 ** i:
				continue
			for j in range(W):
				if w & 2 ** j:
					continue
				if C[i][j] == '#':
					b += 1
		if b == K:
			t += 1
print(t)


import copy
(H, W, K) = map(int, input().split())
tiles = [list(input()) for _ in range(H)]
answer = 0
for h in range(2 ** H):
	for w in range(2 ** W):
		b_cnt = 0
		for i in range(H):
			for j in range(W):
				if not (h >> i & 1 or w >> j & 1) and tiles[i][j] == '#':
					b_cnt += 1
		if b_cnt == K:
			answer += 1
print(answer)


(h, w, k) = map(int, input().split())
c = list((input() for _ in range(h)))
ans = 0
for i in range(1 << h):
	for j in range(1 << w):
		b = 0
		for y in range(h):
			for x in range(w):
				if i >> y & 1 and j >> x & 1 and (c[y][x] == '#'):
					b += 1
		if b == k:
			ans += 1
print(ans)


import math
import copy
import string
INF = int(10 ** 18)
pi = math.pi
MOD = 1000000007

def my_pow(N, a, M):
	if a == 0:
		return 1
	elif a % 2 == 0:
		tempo = my_pow(N, a / 2, M)
		return tempo * tempo % M
	else:
		tempo = my_pow(N, a - 1, M)
		return tempo * N % M

def my_combination(N, a, M):
	res = 1
	for i in range(0, a):
		res *= N - i
		res %= M
	for i in range(0, a):
		res *= my_pow(i + 1, M - 2, M)
		res %= M
	return res

def my_combination_table(N, M, v):
	if len(v) < N + 1:
		l = N + 1 - len(v)
		tempo = [1] * l
		v.extend(tempo)
	for i in range(1, N + 1):
		v[i] = v[i - 1] * (N - (i - 1))
		v[i] %= M
		v[i] *= my_pow(i, M - 2, M)
		v[i] %= M
	return
(H, W, K) = (int(x) for x in input().split())
c = [input() for i in range(0, H)]
res = 0
for i in range(0, 2 ** H):
	for j in range(0, 2 ** W):
		cnt = 0
		for h in range(0, H):
			for w in range(0, W):
				if c[h][w] == '#' and 1 << h & i and 1 << w & j:
					cnt += 1
		if cnt == K:
			res += 1
print(res)


import numpy as np

def main():
	(H, W, K) = list(map(int, input().split()))
	M = np.array([list(input()) for _ in range(H)])
	ans = 0
	for n in range(2 ** (H + W)):
		p = bin(n)[2:]
		p = '0' * (H + W - len(p)) + p
		m = M.copy()
		for i in range(H):
			for j in range(W):
				if p[i] == '1' or p[H + j] == '1':
					m[i][j] = '.'
		cnt = np.count_nonzero(m == '#')
		if cnt == K:
			ans += 1
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


(H, W, K) = map(int, input().split())
mat = [input() for _ in range(H)]
ans = 0
for matR in range(2 ** H):
	for matC in range(2 ** W):
		cnt = 0
		for i in range(H):
			for j in range(W):
				if matR >> i & 1 and matC >> j & 1:
					if mat[i][j] == '#':
						cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(h, w, k) = list(map(int, input().split()))
li = []
for i in range(h):
	li.append(list(input()))
ans = 0
for i in range(1 << h):
	for j in range(1 << w):
		cnt = 0
		for p in range(h):
			for q in range(w):
				if i >> p & 1:
					continue
				if j >> q & 1:
					continue
				if li[p][q] == '#':
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
table = list((input() for i in range(h)))
ans = 0
cnt = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		for s in range(h):
			for t in range(w):
				if table[s][t] == '#' and i >> s & 1 and j >> t & 1:
					cnt += 1
		if cnt == k:
			ans += 1
		cnt = 0
print(ans)


(h, w, k) = map(int, input().split())
chw = [input() for _ in range(h)]
answer = 0
for col in range(2 ** h):
	for row in range(2 ** w):
		black = 0
		for i in range(h):
			for j in range(w):
				if col >> i & 1 and row >> j & 1 and (chw[i][j] == '#'):
					black = black + 1
		if black == k:
			answer += 1
print(answer)


(h, w, k) = map(int, input().split())
c = []
for i in range(h):
	c.append(str(input()))
ans = 0
for m in range(2 ** h):
	for l in range(2 ** w):
		a = 0
		for i in range(h):
			for j in range(w):
				if m >> i & 1 and l >> j & 1 and (c[i][j] == '#'):
					a += 1
		if a == k:
			ans += 1
print(ans)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from itertools import product

def main():
	(h, w, k) = map(int, input().split())
	gg = []
	for _ in range(h):
		row = [1 if c == '#' else 0 for c in list(input())]
		gg.extend(row)
	row_pro = tuple(product((0, 1), repeat=h))
	col_pro = tuple(product((0, 1), repeat=w))
	pat = tuple(product(row_pro, col_pro))
	r = 0
	for pate in pat:
		t0 = 0
		for (i0, p0) in enumerate(pate[0]):
			for (i1, p1) in enumerate(pate[1]):
				if p0 and p1:
					t0 += gg[i0 * w + i1]
		if t0 == k:
			r += 1
	print(r)

def __starting_point():
	main()
__starting_point()


(h, w, k) = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		black = 0
		for i2 in range(h):
			for j2 in range(w):
				if c[i2][j2] == '#' and i >> i2 & 1 == 0 and (j >> j2 & 1 == 0):
					black += 1
		if black == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
grid = []
for row in range(H):
	grid.append(input())
ans = 0
for i in range(1 << H):
	for j in range(1 << W):
		count = 0
		for row in range(H):
			for col in range(W):
				if i >> row & 1 == 1 and j >> col & 1 == 1 and (grid[row][col] == '#'):
					count += 1
		if count == K:
			ans += 1
print(ans)


(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)


(h, w, ka) = map(int, input().split())
mat = [list(input()) for i in range(h)]
ans = 0
for i in range(2 ** (h + w)):
	b = bin(i)[2:].zfill(h + w)
	rs = b[:h]
	cs = b[h:]
	ct = 0
	for l in range(h):
		for k in range(w):
			if mat[l][k] == '#' and rs[l] == '0' and (cs[k] == '0'):
				ct += 1
	if ct == ka:
		ans += 1
print(ans)


from sys import stdin
(H, W, K) = [int(_) for _ in stdin.readline().rstrip().split()]
C = [list(stdin.readline().rstrip()) 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 == 0 and w >> j & 1 == 0 and (C[i][j] == '#'):
					black += 1
		if black == K:
			ans += 1
print(ans)


(h, w, K) = map(int, input().split())
maze = []
cnt = 0
ans = 0
for i in range(h):
	s = input()
	cnt += s.count('#')
	li = [c for c in s]
	maze.append(li)
for i in range(2 ** h):
	c = 0
	height = []
	for j in range(h):
		if i >> j & 1:
			height.append(j)
	for y in height:
		for x in range(w):
			if maze[y][x] == '#':
				c += 1
	for k in range(2 ** w):
		d = 0
		width = []
		for l in range(w):
			if k >> l & 1:
				width.append(l)
		for y in range(h):
			for x in width:
				if maze[y][x] == '#':
					d += 1
		total = c + d
		for y in height:
			for x in width:
				if maze[y][x] == '#':
					total -= 1
		if cnt - total == K:
			ans += 1
print(ans)


(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):
		count = 0
		for ii in range(H):
			for jj in range(W):
				if i >> ii & 1 == 0 and j >> jj & 1 == 0 and (c[ii][jj] == '#'):
					count += 1
		if count == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
S = []
y = 0
for i in range(h):
	S.append(input())
for i in range(2 ** h):
	S2 = []
	for j in range(h):
		if i >> j & 1:
			S2.append(S[j])
	for l in range(2 ** w):
		x = 0
		for m in range(w):
			if l >> m & 1:
				for n in range(len(S2)):
					if S2[n][m] == '#':
						x += 1
		if x == k:
			y += 1
print(y)


(h, w, k) = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
for i in range(1 << h):
	for j in range(1 << w):
		cnt = sum((c[k][l] == '#' for k in range(h) for l in range(w) if i >> k & 1 and j >> l & 1))
		if cnt == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = [input() for _ in range(H)]
ans = 0
for case in range(2 ** (H + W)):
	black = 0
	for i in range(H):
		for j in range(W):
			if case >> i & 1 and case >> j + H & 1 and (c[i][j] == '#'):
				black += 1
	if black == K:
		ans += 1
print(ans)


import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict
import copy
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().strip()
NI = lambda : int(input())
NMI = lambda : map(int, input().split())
NLI = lambda : list(NMI())
SI = lambda : input()

def main():
	(H, W, K) = NMI()
	C = [list(input()) for _ in range(H)]
	ans = 0
	for hi in range(2 ** H):
		for wi in range(2 ** W):
			CC = copy.deepcopy(C)
			for hj in range(H):
				if hi >> hj & 1:
					for x in range(W):
						CC[hj][x] = 'R'
			for wj in range(W):
				if wi >> wj & 1:
					for x in range(H):
						CC[x][wj] = 'R'
			cnt = 0
			for h in range(H):
				cnt += CC[h].count('#')
			if cnt == K:
				ans += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


(H, W, K) = map(int, input().split())
C = [input() for _ in range(H)]
cnt = 0
for i in range(2 ** H):
	for j in range(2 ** W):
		black = 0
		for x in range(H):
			for y in range(W):
				if i >> x & 1 and j >> y & 1 and (C[x][y] == '#'):
					black += 1
		if black == K:
			cnt += 1
print(cnt)


from itertools import product
(h, w, k) = map(int, input().split())
a = 0
c = [[0 if l == '.' else 1 for l in input()] for _ in range(h)]
for i in product([0, 1], repeat=h):
	for j in product([0, 1], repeat=w):
		b = 0
		for (H, W) in product(range(h), range(w)):
			b += c[H][W] * i[H] * j[W]
		if b == k:
			a += 1
print(a)


import itertools
(H, W, K) = map(int, input().split())
c = [input() for _ in range(H)]
ans = 0
for i in list(itertools.product([0, 1], repeat=H + W)):
	a = 0
	for j in range(H):
		if i[j] == 1:
			continue
		for k in range(W):
			if i[H + k] == 1:
				continue
			if c[j][k] == '#':
				a += 1
	if a == K:
		ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [0] * h
for i in range(h):
	c[i] = input()
y = 0
for i in range(2 ** (h + w)):
	x = 0
	a = [0] * (h + w)
	for j in range(h + w):
		if i // 2 ** j % 2 == 1:
			a[j] = 1
	for j in range(h):
		if a[j] == 0:
			for l in range(w):
				if a[h + l] == 0:
					if c[j][l] == '#':
						x += 1
	if x == k:
		y += 1
print(y)


(h, w, k) = list(map(int, input().split()))
c = []
ans = 0
for i in range(h):
	c.append(list(input()))
for i in range(2 ** h):
	for j in range(2 ** w):
		now = 0
		for x in range(h):
			for y in range(w):
				if not i >> x & 1 and (not j >> y & 1) and (c[x][y] == '#'):
					now += 1
		if now == k:
			ans += 1
print(ans)


import numpy as np
(H, W, K) = list(map(int, input().split()))
cmap = []
for i in range(H):
	tmp = input()
	strlist = [s for s in tmp]
	cmap.append(strlist)
cmap = np.array(cmap)

def count_char(cmap, rmask, cmask, num_digits_r, num_digits_c, char='#'):

	def to_bin_str(num, num_digits):
		return str(bin(num))[2:].zfill(num_digits)

	def to_index(mask, num_digits):
		str = to_bin_str(mask, num_digits)
		ids = [i for (i, s) in enumerate(str) if s == '1']
		return ids
	rids = to_index(rmask, num_digits_r)
	cids = to_index(cmask, num_digits_c)
	cmap2 = cmap.copy()
	cmap2[rids, :] = 'r'
	cmap2[:, cids] = 'r'
	count = len(cmap2[cmap2 == char])
	return count
count = 0
for rmask in range(2 ** H):
	for cmask in range(2 ** W):
		num_b = count_char(cmap, rmask, cmask, H, W)
		if num_b == K:
			count += 1
print(count)


(H, W, K) = map(int, input().split())
arr = [list(input()) for _ in range(H)]
ans = 0
for paint_h in range(2 ** H):
	for paint_w in range(2 ** W):
		cnt = 0
		for i in range(H):
			for j in range(W):
				if paint_h >> i & 1 == 0 and paint_w >> j & 1 == 0:
					if arr[i][j] == '#':
						cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
lis = []
ans = 0
for i in range(H):
	lis.append(list(input()))
for i in range(1 << H):
	for j in range(1 << W):
		cnt = 0
		for p in range(H):
			for q in range(W):
				if i >> p & 1:
					continue
				if j >> q & 1:
					continue
				if lis[p][q] == '#':
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(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):
		cnt = 0
		for x in range(h):
			for y in range(w):
				if i >> x & 1:
					continue
				if j >> y & 1:
					continue
				if c[x][y] == '#':
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0
for p in range(1 << h):
	for q in range(1 << w):
		black = 0
		for m in range(h):
			for n in range(w):
				if p >> m & 1 == 0 and q >> n & 1 == 0 and (c[m][n] == '#'):
					black += 1
		if black == k:
			ans += 1
print(ans)


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


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


(H, W, K) = map(int, input().split())
c_map = []
for _ in range(H):
	c = input()
	c_map.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 c_map[k][l] == '#' and i >> k & 1 == 0 and (j >> l & 1 == 0):
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
mat = []
for i in range(h):
	mat.append(list(input()))
cnt = 0
for row in range((1 << h) - 1):
	for col in range((1 << w) - 1):
		black = 0
		for i in range(h):
			for j in range(w):
				if row >> i & 1 == 0 and col >> j & 1 == 0:
					if mat[i][j] == '#':
						black += 1
		if black == k:
			cnt += 1
print(cnt)


(h, w, k) = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for i in range(1 << h):
	for j in range(1 << w):
		t = 0
		for a in range(h):
			for b in range(w):
				if i >> a & 1 and j >> b & 1 and (c[a][b] == '#'):
					t += 1
		if t == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
C = [list(input()) for i in range(H)]
ans = 0
for h in range(1 << H):
	for w in range(1 << W):
		curr = 0
		for i in range(H):
			for j in range(W):
				if not h & 1 << i and (not w & 1 << j) and (C[i][j] == '#'):
					curr += 1
		if K == curr:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = []
for i in range(H):
	c.append(list(input()))
ans = 0
for i in range(1 << H):
	for j in range(1 << W):
		v = 0
		for k in range(H):
			for l in range(W):
				if c[k][l] == '#' and i >> k & 1 == 0 and (j >> l & 1 == 0):
					v += 1
		if v == K:
			ans += 1
print(ans)


(H, W, K) = list(map(int, input().split()))
c = [input() for _ in range(H)]
ans = 0
for R in range(2 ** H):
	for C in range(2 ** W):
		n = 0
		for y in range(H):
			if R >> y & 1:
				for x in range(W):
					if C >> x & 1:
						if c[y][x] == '#':
							n += 1
		if n == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
C = []
for _ in range(h):
	C.append(input())
from itertools import *
ans = 0
for bit in range(1 << h + w):
	c = 0
	for (i, j) in product(range(w, h + w), range(w)):
		if bit >> i & 1 and bit >> j & 1:
			c += C[i - w][j] == '#'
	if c == k:
		ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [input() for _ in range(h)]
ret = 0
for i in range(1 << h):
	for j in range(1 << w):
		cnt = 0
		for x in range(h):
			for y in range(w):
				if c[x][y] == '#' and i >> x & 1 and j >> y & 1:
					cnt += 1
		if cnt == k:
			ret += 1
print(ret)


def two(x, y):
	return (y - len(bin(x)[2:])) * '0' + bin(x)[2:]
(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):
		H = two(i, h)
		W = two(j, w)
		cnt = 0
		for k in range(h):
			for l in range(w):
				if c[k][l] == '#' and H[k] == '0' and (W[l] == '0'):
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
P = []
for i in range(H):
	s = input()
	a = []
	for j in range(W):
		a.append(s[j])
	P.append(a)
ans = 0
for markR in range(2 ** H):
	for markC in range(2 ** W):
		black = 0
		for i in range(H):
			for j in range(W):
				if markR >> i & 1 == 0 and markC >> j & 1 == 0 and (P[i][j] == '#'):
					black += 1
		if black == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for h_p in range(2 ** h):
	for w_p in range(2 ** w):
		cnt = 0
		for i in range(h):
			for j in range(w):
				if h_p >> i & 1 and w_p >> j & 1 and (c[i][j] == '#'):
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


import itertools
(H, W, K) = map(int, input().split())
c = [list(input()) for i in range(H)]
count = 0
for (bit_h, bit_w) in itertools.product(range(1 << H), range(1 << W)):
	black = 0
	for (h, w) in itertools.product(range(H), range(W)):
		if c[h][w] == '#' and bit_h >> h & 1 and bit_w >> w & 1:
			black += 1
	if black == K:
		count += 1
print(count)


(h, w, k) = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
for pattern_h in range(2 ** h):
	for pattern_w in range(2 ** w):
		count = 0
		for i in range(h):
			for j in range(w):
				if pattern_h >> i & 1 == 0 and pattern_w >> j & 1 == 0:
					if c[i][j] == '#':
						count += 1
		if count == k:
			ans += 1
print(ans)


(h, w, K) = map(int, input().split())
C = []
ans = 0
for i in range(h):
	c = input()
	C.append(c)
for i in range(2 ** h):
	for k in range(2 ** w):
		black = 0
		for j in range(h):
			for l in range(w):
				if i >> j & 1 == 0 and k >> l & 1 == 0 and (C[j][l] == '#'):
					black += 1
		if black == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = [['.' for _ in range(W)] for _ in range(H)]
for h in range(H):
	c[h] = input()
ans = 0
for i in range(2 ** H):
	for k in range(2 ** W):
		count = 0
		for h in range(H):
			for w in range(W):
				if i >> h & 1 and k >> w & 1:
					if c[h][w] == '#':
						count += 1
		if count == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
S = [input() for _ in range(h)]
x = 0
for i in range(2 ** h):
	T = [S[j] for j in range(h) if i >> j & 1]
	for l in range(2 ** w):
		U = [row[m] for row in T for m in range(w) if l >> m & 1]
		if U.count('#') == k:
			x += 1
print(x)


import itertools
(h, w, k) = map(int, input().split())
c = []
ans = 0
for i in range(h):
	c.append(list(input()))
for i in range(2 ** h - 1):
	c2 = []
	x = str(bin(i))[2:].zfill(h)
	for a in range(h):
		if x[a] == '0':
			c2.append(c[a])
		elif x[a] == '1':
			c2.append(['*'] * w)
	black = list(itertools.chain.from_iterable(c2)).count('#')
	for j in range(2 ** w - 1):
		black2 = black
		y = str(bin(j))[2:].zfill(w)
		for b in range(w):
			if y[b] == '1':
				for a in range(h):
					if c2[a][b] == '#':
						black2 -= 1
		if black2 == k:
			ans += 1
print(ans)


def main():
	(H, W, K) = map(int, input().split())
	grid = [input() for _ in range(H)]
	n = H + W
	ans = 0
	for case in range(2 ** n):
		cnt = 0
		for i in range(H):
			for j in range(W):
				if case >> i & 1:
					if case >> j + H & 1:
						if grid[i][j] == '#':
							cnt += 1
		if cnt == K:
			ans += 1
	print(ans)
main()


import sys

def input():
	return sys.stdin.readline().rstrip()
from itertools import product

def main():
	(h, w, k) = map(int, input().split())
	C = [input() for _ in range(h)]
	comb_list = list(product([False, True], repeat=h + w))
	ans = 0
	for comb in comb_list:
		cunt = 0
		for i in range(h):
			if not comb[i]:
				continue
			for j in range(w):
				if not comb[h + j]:
					continue
				if C[i][j] == '#':
					cunt += 1
		if cunt == k:
			ans += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


(h, w, k) = map(int, input().split())
m = [[] for _ in range(h)]
for y in range(h):
	m[y] = list(input())
ans = 0
for y in range(1 << h):
	for x in range(1 << w):
		(mx, my) = ([], [])
		for y2 in range(h):
			if y >> y2 & 1:
				my.append(y2)
		for x2 in range(w):
			if x >> x2 & 1:
				mx.append(x2)
		cnt = 0
		for y2 in my:
			for x2 in mx:
				if m[y2][x2] == '#':
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = []
for i in range(h):
	c += [input()]
ans = 0
for i in range(2 ** (w + h)):
	count = 0
	for y in range(h):
		for x in range(w):
			if c[y][x] == '#' and i >> x & 1 == 0 and (i >> y + w & 1 == 0):
				count += 1
	if count == k:
		ans += 1
print(ans)


(h, w, k) = map(int, input().split(' '))
c = [input() for x in range(h)]
cnt = 0
for maskR in range(2 ** h):
	for maskC in range(2 ** w):
		black = 0
		for i in range(h):
			for j in range(w):
				if maskR >> i & 1 == 0 and maskC >> j & 1 == 0 and (c[i][j] == '#'):
					black += 1
		if black == k:
			cnt += 1
print(cnt)


(H, W, K) = map(int, input().split())
nums = list((list(input()) for i in range(H)))
ans = 0
for i in range(2 ** H):
	for j in range(2 ** W):
		c = 0
		for x in range(H):
			for y in range(W):
				if i >> x & 1 == 0 and j >> y & 1 == 0:
					if nums[x][y] == '#':
						c += 1
		if c == K:
			ans += 1
print(ans)


from itertools import product
import numpy as np
(H, W, K) = list(map(int, input().split()))
C = []
for _ in range(H):
	tmp = [m for m in map(str, input())]
	C.append(tmp)
C = np.array(C)
ans = 0
for h in product(list(range(2)), repeat=H):
	for w in product(list(range(2)), repeat=W):
		cnt = 0
		for ih in range(H):
			for iw in range(W):
				if C[ih, iw] == '#' and (h[ih] and w[iw]):
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


import itertools
import copy
(H, W, K) = list(map(int, input().split()))
c = [list(str(input())) for i in range(H)]
ans = 0
H_bit = list(itertools.product([0, 1], repeat=H))
W_bit = list(itertools.product([0, 1], repeat=W))

def mark(h, w, board):
	for (i, n) in enumerate(h):
		if n == 1:
			board[i] = ['R'] * W
	for (j, n) in enumerate(w):
		if n == 1:
			for k in range(H):
				board[k][j] = 'R'
	return board
for i in H_bit:
	for j in W_bit:
		check = copy.deepcopy(c)
		li = mark(i, j, check)
		if sum((a.count('#') for a in li)) == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
s = [list(input()) for i in range(H)]
ans = 0
for i in range(1 << H):
	for j in range(1 << W):
		cnt = 0
		for h in range(H):
			for w in range(W):
				if i >> h & 1 == 1 and j >> w & 1 == 1:
					if s[h][w] == '#':
						cnt += 1
		if cnt == K:
			ans += 1
print(ans)


import itertools as it
(n, m, k) = list(map(int, input().split()))
S = [list(str(input())) for h in range(n)]
ans = 0
for i in it.product([0, 1], repeat=n):
	for j in it.product(range(2), repeat=m):
		count = 0
		for h in range(n):
			for c in range(m):
				if S[h][c] == '#' and i[h] + j[c] == 0:
					count += 1
		if count == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
B = [list(input()) for _ in range(H)]
T = 0
for i_1 in range(2 ** H):
	for i_2 in range(2 ** W):
		X = [j_1 for j_1 in range(H) if i_1 >> j_1 & 1]
		Y = [j_2 for j_2 in range(W) if i_2 >> j_2 & 1]
		S = 0
		for x in X:
			for y in Y:
				if B[x][y] == '#':
					S += 1
		if S == K:
			T += 1
print(T)


(h, w, k) = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
for row in range(2 ** h):
	for col in range(2 ** w):
		c = 0
		for i in range(h):
			for j in range(w):
				if row >> i & 1 == 0 and col >> j & 1 == 0:
					if s[i][j] == '#':
						c += 1
		if c == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
C = []
for _ in range(h):
	C.append(input())
ans = 0
for hbit in range(1 << h):
	for wbit in range(1 << w):
		c = 0
		for i in range(h):
			for j in range(w):
				if hbit >> i & 1 and wbit >> j & 1 and (C[i][j] == '#'):
					c += 1
		if c == k:
			ans += 1
print(ans)


from itertools import product
(h, w, k) = list(map(int, input().split()))
c = [input() for i in range(h)]
ans = 0
for row_bit in product(list(range(2)), repeat=h):
	for col_bit in product(list(range(2)), repeat=w):
		count = 0
		for row in range(h):
			for col in range(w):
				if c[row][col] == '#' and (row_bit[row] and col_bit[col]):
					count += 1
		if count == k:
			ans += 1
print(ans)


import itertools
import numpy as np
(H, W, K) = list(map(int, input().split()))
c_table = []
for _ in range(H):
	c_list = input()
	c_list = [0 if c == '.' else 1 for c in list(c_list)]
	c_table.append(c_list)
h_patterns = list(itertools.product([True, False], repeat=H))
w_patterns = list(itertools.product([True, False], repeat=W))
count = 0
for h_p in h_patterns:
	for w_p in w_patterns:
		w_table = np.array(c_table)
		for (i, h_flag) in enumerate(h_p):
			if h_flag:
				w_table[i] = 0
			for (j, w_flag) in enumerate(w_p):
				if w_flag:
					w_table.T[j] = 0
		if w_table.sum() == K:
			count += 1
ans = count
print(ans)


import itertools as it
(H, W, N) = map(int, input().split())
c = [list(input()) for t in range(H)]
ans = 0
for con in it.product(range(2), repeat=H):
	for row in it.product(range(2), repeat=W):
		count = 0
		for h in range(H):
			for w in range(W):
				if c[h][w] == '#' and con[h] == 1 and (row[w] == 1):
					count += 1
		if count == N:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
board = [[-1 for j in range(w)] for i in range(h)]
for i in range(h):
	color = input()
	for j in range(w):
		if color[j] == '#':
			board[i][j] = 1
		else:
			board[i][j] = 0
ans = 0
for row_choose in range(1 << h):
	for col_choose in range(1 << w):
		count = 0
		for i in range(h):
			for j in range(w):
				if not row_choose & 1 << i and (not col_choose & 1 << j) and board[i][j]:
					count += 1
		if count == k:
			ans += 1
print(ans)


(H, W, K) = list(map(int, input().split()))
table = [input() for _ in range(H)]
ans = 0
for mask_h in range(2 ** H):
	for mask_w in range(2 ** W):
		black = 0
		for i in range(H):
			for j in range(W):
				if mask_h >> i & 1 == 0 and mask_w >> j & 1 == 0 and (table[i][j] == '#'):
					black += 1
		if black == K:
			ans += 1
print(str(ans))


(h, w, k) = map(int, input().split())
c = []
for _ in range(h):
	c.append(list(input()))
ans = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		q = 0
		for i_ in range(h):
			for j_ in range(w):
				if i >> i_ & 1 and j >> j_ & 1 and (c[i_][j_] == '#'):
					q += 1
		if q == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = [input() for _ in range(H)]
ans = 0
for i in range(1 << H):
	for j in range(1 << W):
		cnt = 0
		for k in range(H):
			if i >> k & 1:
				continue
			for l in range(W):
				if j >> l & 1:
					continue
				if c[k][l] == '#':
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(h, w, n) = map(int, input().split())
test = [input() for i in range(h)]
ans = 0
for binh in range(2 ** h):
	for binw in range(2 ** w):
		tmp = 0
		for l in range(h):
			for m in range(w):
				if binh >> l & 1 == 0 and binw >> m & 1 == 0 and (test[l][m] == '#'):
					tmp += 1
		if tmp == n:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
S = [input() for i in range(H)]
P = 0
Q = 0
for i in range(1 << H):
	for j in range(1 << W):
		Q = 0
		for k in range(H):
			for l in range(W):
				if S[k][l] == '#' and i & 1 << k != 0 and (j & 1 << l != 0):
					Q += 1
		if Q == K:
			P += 1
print(P)


(H, W, K) = [int(v) for v in input().split()]
G = []
for _ in range(H):
	G.append(input())
ans = 0
for mask_r in range(1 << H):
	for mask_c in range(1 << W):
		black = 0
		for i in range(H):
			for j in range(W):
				if mask_r >> i & 1 == 0 and mask_c >> j & 1 == 0 and (G[i][j] == '#'):
					black += 1
		if black == K:
			ans += 1
print(ans)


(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):
		c = 0
		for ii in range(H):
			for jj in range(W):
				if 1 & i >> ii & j >> jj:
					if C[ii][jj] == '#':
						c += 1
		if c == K:
			ans += 1
print(ans)


from copy import deepcopy as copy
(H, W, K) = list(map(int, input().split()))
c = [list(input()) for i in range(H)]
ans = 0
for i in range(2 ** H):
	cc = copy(c)
	n = i
	idx = -1
	while n > 0:
		x = n % 2
		n //= 2
		idx += 1
		if x == 0:
			continue
		for j in range(W):
			cc[idx][j] = '.'
	for j in range(2 ** W):
		ccc = copy(cc)
		n = j
		idx = -1
		while n > 0:
			x = n % 2
			n //= 2
			idx += 1
			if x == 0:
				continue
			for k in range(H):
				ccc[k][idx] = '.'
		cnt = sum([_.count('#') for _ in ccc])
		if cnt == K:
			ans += 1
print(ans)


from itertools import product
(H, W, K) = list(map(int, input().split()))
C = []
for _ in range(H):
	c = list(input())
	C.append(c)
ans = 0
for row_bit in product(list(range(2)), repeat=H):
	for col_bit in product(list(range(2)), repeat=W):
		cnt = 0
		for row in range(H):
			for col in range(W):
				if C[row][col] == '#' and (row_bit[row] and col_bit[col]):
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(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):
		count = 0
		for i in range(H):
			for j in range(W):
				if c[i][j] == '#' and row & 1 << i == 0 and (col & 1 << j == 0):
					count += 1
		if count == K:
			ans += 1
print(ans)


(h, w, k) = [int(i) for i in input().split()]
c = [input() for i in range(h)]
cnt = 0
for i in range(1 << h):
	bit_h = [0] * h
	for j in range(h):
		bit_h[j] = int(i & 1 << j > 0)
	for j in range(1 << w):
		bit_w = [0] * w
		for l in range(w):
			bit_w[l] = int(j & 1 << l > 0)
		cnt_t = 0
		for m in range(h):
			for n in range(w):
				if bit_h[m] == 0 and bit_w[n] == 0 and (c[m][n] == '#'):
					cnt_t += 1
		if cnt_t == k:
			cnt += 1
print(cnt)


(h, w, k) = map(int, input().split())
m = [list(input()) for i in range(h)]
o = 0
for h_bit in range(2 ** h):
	for w_bit in range(2 ** w):
		c = 0
		for i in range(h):
			for j in range(w):
				if h_bit >> i & 1 == 0 and w_bit >> j & 1 == 0 and (m[i][j] == '#'):
					c += 1
		if c == k:
			o += 1
print(o)


import copy

def count(w, h):
	Dtemp = copy.deepcopy(Data)
	for i in range(W):
		if 1 << i & w != 0:
			for hh in range(H):
				Dtemp[hh][i] = 'R'
	for i in range(H):
		if 1 << i & h != 0:
			for ww in range(W):
				Dtemp[i][ww] = 'R'
	c = 0
	for hh in range(H):
		for ww in range(W):
			if Dtemp[hh][ww] == '#':
				c += 1
	return c
(H, W, K) = map(int, input().split())
Data = []
for _ in range(H):
	s = input()
	l = []
	for c in s:
		l.append(c)
	Data.append(l)
ans = 0
for w in range(0, 2 ** W):
	for h in range(0, 2 ** H):
		if count(w, h) == K:
			ans += 1
print(ans)


(h, w, K) = map(int, input().split())
masu = [input() for _ in range(h)]
ans = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		cnt = 0
		for k in range(h):
			for l in range(w):
				if i >> k & 1 and j >> l & 1 and (masu[k][l] == '#'):
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(h, w, K) = map(int, input().split())
c = []
for i in range(h):
	a = list(str(input()))
	c.append(a)
cnt = 0
blk = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		for k in range(h):
			for l in range(w):
				if i >> k & 1 == 0 and j >> l & 1 == 0 and (c[k][l] == '#'):
					blk += 1
		if blk == K:
			cnt += 1
		blk = 0
print(cnt)


import numpy as np
from itertools import combinations
(h, w, k) = map(int, input().split())
graph = []
for i in range(h):
	row = [1 if x == '#' else 0 for x in input()]
	graph.append(row)
graph = np.array(graph)
h_combi = []
w_combi = []
for i in range(1, h + 1):
	h_combi.extend(list(combinations(range(h), i)))
for i in range(1, w + 1):
	w_combi.extend(list(combinations(range(w), i)))
ans = 0
for hi in h_combi:
	for wi in w_combi:
		cnt = 0
		for y in hi:
			if cnt > k:
				break
			for x in wi:
				cnt += graph[y][x]
		if cnt == k:
			ans += 1
print(ans)


import itertools
(H, W, K) = map(int, input().split())
C = [input() for i in range(H)]
ans = 0
for paint_H in itertools.product([0, 1], repeat=H):
	for paint_W in itertools.product([0, 1], repeat=W):
		cnt = 0
		for i in range(H):
			for j in range(W):
				if paint_H[i] == 0 and paint_W[j] == 0 and (C[i][j] == '#'):
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
m = []
A = 0
for _ in range(H):
	m.append([v for v in input()])
for h in range(2 ** H):
	for w in range(2 ** W):
		ans = 0
		for h2 in range(H):
			for w2 in range(W):
				if h >> h2 & 1 and w >> w2 & 1 and (m[h2][w2] == '#'):
					ans += 1
		if ans == K:
			A += 1
print(A)


(h, w, k) = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for bit in range(1 << h + w):
	cnt = 0
	for i in range(h):
		if bit >> i & 1:
			continue
		for j in range(w):
			if bit >> h + j & 1:
				continue
			if c[i][j] == '#':
				cnt += 1
	if cnt == k:
		ans += 1
print(ans)


import itertools
(h, w, k) = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0
for filter_row in range(2 ** h):
	for filter_col in range(2 ** w):
		cnt = 0
		for i in range(h):
			for j in range(w):
				if filter_row >> i & 1 != 0 and filter_col >> j & 1 != 0 and (c[i][j] == '#'):
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


import sys
(h, w, k) = map(int, input().split())
s = sys.stdin.readlines()
ans = 0
for ib in range(1 << h):
	for jb in range(1 << w):
		cnt = 0
		for i in range(h):
			if ib >> i & 1:
				continue
			for j in range(w):
				if jb >> j & 1:
					continue
				if s[i][j] == '#':
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = [tuple(input()) for i in range(H)]
ans = 0
for i in range(2 ** H):
	s = i
	b = [list(x) for x in c]
	for j in range(H):
		if s >= 2 ** (H - j - 1):
			s -= 2 ** (H - j - 1)
			b[j] = ['.'] * W
	b = list(zip(*b))
	for k in range(2 ** W):
		bt = [list(x) for x in b]
		t = k
		for l in range(W):
			if t >= 2 ** (W - l - 1):
				t -= 2 ** (W - l - 1)
				bt[l] = ['.'] * H
		u = sum((bt[m].count('#') for m in range(W)))
		if u == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
List = [list(input()) for _ in range(H)]
MAP = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
	for j in range(W):
		if List[i][j] == '#':
			MAP[i][j] = 1
MAPP = [[0 for j in range(W)] for i in range(H)]
bx = [0] * W
by = [0] * H
c = [0] * 2 ** H * 2 ** W
for i in range(2 ** H * 2 ** W):
	b = format(i, 'b').zfill(H + W)
	for jx in range(W):
		bx[jx] = int(b[-W + jx])
	for jy in range(H):
		by[jy] = int(b[jy])
	for k in range(H):
		for l in range(W):
			MAPP[k][l] = MAP[k][l] * bx[l] * by[k]
	c[i] = sum(map(sum, MAPP))
print(c.count(K))


(H, W, K) = map(int, input().split())
C = [list(input()) for h in range(H)]
ans = 0
for h in range(2 ** H):
	for w in range(2 ** W):
		c = 0
		for i in range(H):
			for j in range(W):
				if h >> i & 1 == 0 and w >> j & 1 == 0 and (C[i][j] == '#'):
					c += 1
		if c == K:
			ans += 1
print(ans)


(n, m, k) = map(int, input().split())
mat = [list(input()) for _ in range(n)]
t = 0
for b in range(1 << n + m):
	c = 0
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '#' and (not (1 << i & b or 1 << j + n & b)):
				c += 1
	if c == k:
		t += 1
print(t)


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] == '#':
				cnt += 1
	if cnt == k:
		ans += 1
print(ans)


(h, w, k) = map(int, input().split())
A = [input() for _ in range(h)]
ans = 0
for gyou in range(2 ** h):
	for retsu in range(2 ** w):
		black = 0
		for x in range(h):
			for y in range(w):
				if gyou >> x & 1 == 0 and retsu >> y & 1 == 0 and (A[x][y] == '#'):
					black = black + 1
		if black == k:
			ans = ans + 1
print(ans)


def main():
	(a, b, c) = list(map(int, input().split()))
	s = [list(map(str, input())) for i in range(a)]
	cnt = 0
	count = 0
	for i in range(2 ** a):
		for j in range(2 ** b):
			cnt = 0
			for ia in range(a):
				for ib in range(b):
					if not i & 1 << ia and (not j & 1 << ib):
						if s[ia][ib] == '#':
							cnt += 1
			if cnt == c:
				count += 1
	print(count)

def __starting_point():
	main()
__starting_point()


from copy import deepcopy
(h, w, kkk) = map(int, input().split())
c = [list(input()) for _ in range(h)]
cnt = 0
for i in range(2 ** h - 1):
	nuritubu_row = []
	for k in range(i):
		if i >> k & 1:
			nuritubu_row.append(k)
	for j in range(2 ** w - 1):
		nuritubu_col = []
		for k in range(j):
			if j >> k & 1:
				nuritubu_col.append(k)
		c_tmp = deepcopy(c)
		for x in range(h):
			for y in range(w):
				if x in nuritubu_row or y in nuritubu_col:
					c_tmp[x][y] = 'o'
		if sum([c_tmp[k].count('#') for k in range(h)]) == kkk:
			cnt += 1
print(cnt)


(h, w, k) = map(int, input().split())
c = []
for i in range(h):
	cc = input()
	c.append(cc)
ans = 0
for i in range(1 << h):
	for j in range(1 << w):
		b = 0
		for ii in range(h):
			for jj in range(w):
				if i >> ii & 1 == 0 and j >> jj & 1 == 0:
					if c[ii][jj] == '#':
						b += 1
		if b == k:
			ans += 1
print(ans)


from itertools import product
(h, w, k) = list(map(int, input().split()))
c = [input() for i in range(h)]
ans = 0
for maskR in product([0, 1], repeat=h):
	for maskC in product([0, 1], repeat=w):
		b = 0
		for i in range(h):
			for j in range(w):
				if maskR[i] == 1 and maskC[j] == 1 and (c[i][j] == '#'):
					b += 1
		if b == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
for row_bin in range(2 ** h):
	for col_bin in range(2 ** w):
		cnt = 0
		for i in range(h):
			for j in range(w):
				if c[i][j] == '#' and (row_bin >> i & 1 and col_bin >> j & 1):
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
S = [input() for _ in range(H)]
(hbit, wbit) = (1 << H, 1 << W)
cnt = 0
for i in range(hbit):
	for j in range(wbit):
		ccnt = 0
		for k in range(H):
			for l in range(W):
				if not (i >> k & 1) + (j >> l & 1):
					ccnt += S[k][l] == '#'
		cnt += ccnt == K
print(cnt)


(H, W, K) = map(int, input().split())
c = list((list(input()) for _ in range(H)))
ans = 0
for i in range(2 ** H):
	for j in range(2 ** W):
		b = 0
		for k in range(H):
			for l in range(W):
				if i >> k & 1 and j >> l & 1 and (c[k][l] == '#'):
					b += 1
		if b == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
board = [list(input()) for _ in range(h)]
ans = 0
for paint_h in range(2 ** h):
	for paint_w in range(2 ** w):
		cnt = 0
		for i in range(h):
			for j in range(w):
				if paint_h >> i & 1 == 0 and paint_w >> j & 1 == 0 and (board[i][j] == '#'):
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
C = [input() for i in range(H)]
B = ''.join(C).count('#')
from itertools import product
a = 0
for p in product((0, 1), repeat=H + W):
	b = B
	for h in range(H):
		for w in range(W):
			if C[h][w] == '#' and (p[h] or p[H + w]):
				b -= 1
	if b == K:
		a += 1
print(a)


(H, W, K) = map(int, input().split())
matrix = [input() for _ in range(H)]
ans = 0
for maskR in range(1 << H):
	for maskC in range(1 << W):
		black = 0
		for i in range(H):
			for j in range(W):
				if maskR >> i & 1 == 0 and maskC >> j & 1 == 0 and (matrix[i][j] == '#'):
					black += 1
		if black == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = [list(input()) for _ in range(H)]
ans = 0
for i in range(1 << H):
	for j in range(1 << W):
		cnt = 0
		for x in range(H):
			for y in range(W):
				if i >> x & 1 == 1 and j >> y & 1 and (c[x][y] == '#'):
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = [input() for _ in range(H)]
ans = 0
for i in range(1 << H):
	for j in range(1 << W):
		count = 0
		for k in range(H):
			for l in range(W):
				if c[k][l] == '#' and i >> k & 1 and j >> l & 1:
					count += 1
		if count == K:
			ans += 1
print(ans)


(H, W, K) = list(map(int, input().split()))
G = []
for _ in range(H):
	G.append(input())
ans = 0
black = 0
for mask_h in range(1 << H):
	for mask_w in range(1 << W):
		black = 0
		for i in range(H):
			for j in range(W):
				if mask_h >> i & 1 == 0 and mask_w >> j & 1 == 0 and (G[i][j] == '#'):
					black += 1
		if black == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = []
for _ in range(h):
	c.append([c for c in input()])
ans = 0
for i in range(1 << h):
	for j in range(1 << w):
		cnt = 0
		for n in range(h):
			for m in range(w):
				if i >> n & 1:
					continue
				if j >> m & 1:
					continue
				if c[n][m] == '#':
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = []
for i in range(H):
	c.append(input())
Hrange = 2 ** H
Wrange = 2 ** W
ans = 0
for h in range(Hrange):
	for w in range(Wrange):
		cnt = 0
		for i in range(H):
			for j in range(W):
				if c[i][j] == '#' and h >> i & 1 and w >> j & 1:
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


def bitmake(digit):
	bit_list = list()
	for i in range(2 ** digit):
		bit = []
		for j in range(digit):
			if i >> j & 1:
				bit.append(j)
		bit_list.append(bit)
	return bit_list
(h, w, k) = list(map(int, input().split()))
grid = [''] * h
for i in range(h):
	grid[i] = list(map(str, input()))
bit_list = bitmake(h + w)
blackh = [0] * h
blackw = [0] * w
blacksum = 0
for i in range(h):
	for j in range(w):
		if grid[i][j] == '#':
			blackh[i] += 1
			blackw[j] += 1
			grid[i][j] = 1
			blacksum += 1
		else:
			grid[i][j] = 0
ans = 0
for i in range(2 ** (h + w)):
	bit = bit_list[i]
	remove = 0
	hight = []
	width = []
	for j in range(len(bit)):
		l = bit[j]
		if l <= h - 1:
			remove += blackh[l]
			hight.append(l)
		else:
			ind = l - h
			remove += blackw[ind]
			width.append(ind)
	rid = 0
	for j in range(len(hight)):
		for l in range(len(width)):
			if grid[hight[j]][width[l]] == 1:
				rid += 1
	if blacksum - remove + rid == k:
		ans += 1
print(ans)


(H, W, K) = map(int, input().split())
C = [input() for _ in range(H)]
a = 0
for i in range(2 ** H):
	for j in range(2 ** W):
		b = 0
		for x in range(H):
			for y in range(W):
				if (2 ** x & i) * (2 ** y & j):
					b += C[x][y] == '#'
		if b == K:
			a += 1
print(a)


(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):
		c = 0
		for ci in range(H):
			for cj in range(W):
				if i >> ci & 1 and j >> cj & 1 and (C[ci][cj] == '#'):
					c += 1
		if c == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = []
for i in range(h):
	c.append(input())
ans = 0
for i in range(1 << h):
	for j in range(1 << w):
		cnt = 0
		for y in range(h):
			if i >> y & 1:
				continue
			for x in range(w):
				if j >> x & 1:
					continue
				if c[y][x] == '#':
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


from itertools import product
(h, w, k) = map(int, input().split())
table = [list(input()) for i in range(h)]
count = 0
for rbit in product(range(2), repeat=h):
	for cbit in product(range(2), repeat=w):
		black = 0
		for row in range(h):
			for col in range(w):
				if table[row][col] == '#' and rbit[row] == 0 and (cbit[col] == 0):
					black += 1
		if black == k:
			count += 1
print(count)


(h, w, q) = map(int, input().split())
c2 = [input() for _ in range(h)]
ans = 0
for i in range(1 << w):
	for j in range(1 << h):
		b = 0
		for x in range(w):
			for y in range(h):
				if i >> x & 1 == 0 and j >> y & 1 == 0 and (c2[y - 1][x - 1] == '#'):
					b += 1
		if b == q:
			ans += 1
print(ans)


(h, w, k) = list(map(int, input().split()))
c = [list(input()) for _ in range(h)]
ans = 0
from itertools import product
for row_bit in product(range(2), repeat=h):
	for col_bit in product(range(2), repeat=w):
		black_cnt = 0
		for i in range(h):
			for j in range(w):
				if c[i][j] == '#' and (row_bit[i] == 0 and col_bit[j] == 0):
					black_cnt += 1
		if black_cnt == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
ccc = [input() for _ in range(h)]
ans = 0
for bit_h in range(2 ** h):
	for bit_w in range(2 ** w):
		cnt = 0
		for hi in range(h):
			for wi in range(w):
				if bit_h >> hi & 1 == 0 and bit_w >> wi & 1 == 0:
					if ccc[hi][wi] == '#':
						cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
a = [input() for _ in range(h)]
ans = 0
for H in range(2 ** h):
	for W in range(2 ** w):
		c = 0
		for i in range(h):
			for j in range(w):
				if H >> i & 1 and W >> j & 1 and (a[i][j] == '#'):
					c += 1
		if c == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
C = [[i for i in input()] for j in range(H)]
ans = 0
for h_bit in range(1 << H):
	for w_bit in range(1 << W):
		black = 0
		for i in range(H):
			for j in range(W):
				if h_bit & 1 << i and w_bit & 1 << j:
					if C[i][j] == '#':
						black += 1
		if black == K:
			ans += 1
print(ans)


import copy
(h, w, k) = map(int, input().split())
data = [input() for i in range(h)]
ans = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		cp = copy.deepcopy(data)
		cnt = 0
		for a in range(h):
			for l in range(w):
				if i >> a & 1 == 1 and j >> l & 1 == 1 and (cp[a][l] == '#'):
					cnt += 1
		if k == cnt:
			ans += 1
print(ans)


from itertools import product
(h, w, k) = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
for i in product([0, 1], repeat=h):
	for j in product([0, 1], repeat=w):
		temp = 0
		for m in range(h):
			for n in range(w):
				if i[m] == 0 and j[n] == 0 and (c[m][n] == '#'):
					temp += 1
		if temp == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0
for maskR in range(1 << h):
	for maskC in range(1 << w):
		black = 0
		for i in range(h):
			for j in range(w):
				if maskR >> i & 1 == 0 and maskC >> j & 1 == 0 and (c[i][j] == '#'):
					black += 1
		if black == k:
			ans += 1
print(ans)


(n, m, k) = map(int, input().split())
w = []
for _ in range(n):
	w.append(input())
sol = 0
for rm in range(1 << n):
	for cm in range(1 << m):
		x = 0
		for i in range(n):
			for j in range(m):
				if rm & 1 << i and cm & 1 << j and (w[i][j] == '#'):
					x += 1
		if x == k:
			sol += 1
print(sol)


(h, w, k) = map(int, input().split())
dic = {}
for i in range(h):
	s = input()
	for j in range(w):
		if s[j] == '#':
			dic[i, j] = 1
res = 0
for ibit in range(2 ** h):
	for jbit in range(2 ** w):
		cnt = 0
		for tpl in dic:
			if ibit >> tpl[0] & 1 and jbit >> tpl[1] & 1:
				cnt += 1
		if cnt == k:
			res += 1
print(res)


(h, w, k) = map(int, input().split())
c = [input() for _ in range(h)]
count = 0
for H in range(1 << h):
	for W in range(1 << w):
		b = 0
		for i in range(h):
			for j in range(w):
				if H >> i & 1 == 0 and W >> j & 1 == 0 and (c[i][j] == '#'):
					b += 1
		if b == k:
			count += 1
print(count)


(H, W, K) = map(int, input().split())
c = [input() for _ in range(H)]
r = [[0] * W for _ in range(H)]
S = 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:
					if j >> l & 1:
						if c[k][l] == '#':
							cnt += 1
		if cnt == K:
			S += 1
print(S)


import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp
INF = inf
MOD = 1000000007
(h, w, k) = [int(i) for i in input().split()]
C = [input() for j in range(h)]
tmp = 0
res = 0
for r in range(h):
	for c in range(w):
		if C[r][c] == '#':
			tmp += 1
for i in range(2 ** h):
	for j in range(2 ** w):
		rs = f'{i:0{h}b}'
		cs = f'{j:0{w}b}'
		tmp_2 = 0
		for r in range(h):
			for c in range(w):
				if (rs[r] == '1' or cs[c] == '1') and C[r][c] == '#':
					tmp_2 += 1
		if tmp - tmp_2 == k:
			res += 1
print(res)


import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect
import sys
import random
import time
import copy
inf = 10 ** 9

def main():
	(h, w, k) = list(map(int, input().split()))
	c = []
	for i in range(h):
		c.append(list(input()))
	r = 0
	for i in range(2 ** h):
		for j in range(2 ** w):
			bh = list(str(bin(i))[2:].zfill(h))
			bw = list(str(bin(j))[2:].zfill(w))
			count = 0
			for m in range(h):
				for l in range(w):
					if bh[m] == '1' and bw[l] == '1' and (c[m - 1][l - 1] == '#'):
						count += 1
			if count == k:
				r += 1
	print(r)

def __starting_point():
	main()
__starting_point()


import itertools
(H, W, K) = map(int, input().split())
G = [input() for i in range(H)]
ans = 0
for i in itertools.product(range(2), repeat=H):
	for j in itertools.product(range(2), repeat=W):
		black = 0
		for h in range(H):
			for w in range(W):
				if i[h] == 0 and j[w] == 0 and (G[h][w] == '#'):
					black += 1
		ans += black == K
print(ans)


(h, w, k) = map(int, input().split())
c = [input() for x in range(h)]
ans = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		count = 0
		for m in range(h):
			for n in range(w):
				if i >> m & 1 == 0 and j >> n & 1 == 0 and (c[m][n] == '#'):
					count += 1
		if count == k:
			ans += 1
print(ans)


(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):
		a = bin(i)[2:].zfill(H)
		b = bin(j)[2:].zfill(W)
		cnt = sum([x + y == '00' and c[k][l] == '#' for (k, x) in enumerate(a) for (l, y) in enumerate(b)])
		if cnt == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [input() for i in range(h)]
ans = 0
for h_1 in range(1 << h):
	for w_1 in range(1 << w):
		black = 0
		for i in range(h):
			for j in range(w):
				if h_1 >> i & 1 == 0 and w_1 >> j & 1 == 0 and (c[i][j] == '#'):
					black += 1
		if black == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
C = [input() for _ in range(h)]
count = 0
for i in range(2 ** h):
	for l in range(2 ** w):
		tmp = ''
		for j in range(h):
			for m in range(w):
				if i >> j & 1 and l >> m & 1:
					tmp += C[j][m]
		if tmp.count('#') == k:
			count += 1
print(count)


import copy
(h, w, k) = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
for i in range(1 << h):
	for j in range(1 << w):
		a = 0
		ci = copy.deepcopy(c)
		for s in range(h):
			if i >> s & 1 == 1:
				for tw in range(w):
					ci[s][tw] = '.'
		for t in range(w):
			if j >> t & 1 == 1:
				for sh in range(h):
					ci[sh][t] = '.'
		for ss in range(h):
			for tt in range(w):
				if ci[ss][tt] == '#':
					a += 1
		if a == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
for ib in range(1 << h):
	for jb in range(1 << w):
		black = 0
		for i in range(h):
			if ib & 1 << i:
				continue
			for j in range(w):
				if jb & 1 << j:
					continue
				black += c[i][j] == '#'
		if black == k:
			ans += 1
print(ans)


(h, w, x) = map(int, input().split())
a = [list(input()) for i in range(h)]
ans = 0
for i in range(2 ** (h + w)):
	b = 0
	for j in range(h):
		for k in range(w):
			if i >> j & 1 == 1 and i >> k + h & 1 == 1 and (a[j][k] == '#'):
				b += 1
	if b == x:
		ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = [input() for i in range(H)]
a = 0
from itertools import product
for i in product([0, 1], repeat=H):
	for j in product([0, 1], repeat=W):
		t = 0
		for k in range(H):
			for l in range(W):
				if i[k] and j[l] and (c[k][l] == '#'):
					t += 1
		if t == K:
			a += 1
print(a)


(h, w, k) = list(map(int, input().split()))
s = [list(map(str, list(input()))) for i in range(h)]
ans = 0
for ii in range(1 << h):
	for jj in range(1 << w):
		cnt = 0
		for i in range(h):
			for j in range(w):
				if ii >> i & 1:
					continue
				if jj >> j & 1:
					continue
				if s[i][j] == '#':
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


from itertools import groupby, accumulate, product, permutations, combinations
(h, w, k) = map(int, input().split())
l = [input() for i in range(h)]
ans = 0
for i in product([0, 1], repeat=h):
	for j in product([0, 1], repeat=w):
		Ans = 0
		for m in range(h):
			for n in range(w):
				if l[m][n] == '#' and i[m] == 1 and (j[n] == 1):
					Ans += 1
		if Ans == k:
			ans += 1
print(ans)


import copy
(h, w, k) = map(int, input().split())
M = [list(input()) for _ in range(h)]
a = 0
for i in range(2 ** w):
	for j in range(2 ** h):
		b = 0
		for c in range(w):
			for r in range(h):
				if i >> c & 1 == 0 and j >> r & 1 == 0 and (M[r][c] == '#'):
					b += 1
		if b == k:
			a += 1
print(a)


(H, W, K) = map(int, input().split())
C = []
for _ in range(H):
	C.append(list(input()))
ans = 0
for bith in range(1 << H):
	for bitw in range(1 << W):
		black = 0
		for h in range(H):
			for w in range(W):
				if C[h][w] == '#' and bith & 1 << h and bitw & 1 << w:
					black += 1
		if black == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
l = [list(input()) for i in range(h)]
res = 0
for hh in range(2 ** h):
	for ww in range(2 ** w):
		cnt = 0
		for i in range(h):
			for j in range(w):
				if hh >> i & 1 == 0 and ww >> j & 1 == 0:
					if l[i][j] == '#':
						cnt += 1
		if cnt == k:
			res += 1
print(res)


(h, w, k) = map(int, input().split())
Black = []
for i in range(h):
	c = input()
	for j in range(w):
		if c[j] == '#':
			Black.append((i, j))
ans = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		a = len(Black)
		for b in Black:
			if i >> b[0] & 1 or j >> b[1] & 1:
				a -= 1
		if a == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
x = [input() for i in range(H)]
x = list(map(list, x))
ans = 0
for i in range(2 ** H):
	for j in range(2 ** W):
		count = 0
		for l in range(H):
			for m in range(W):
				if i >> l & 1 and j >> m & 1 and (x[l][m] == '#'):
					count += 1
		if count == K:
			ans += 1
print(ans)


from copy import deepcopy
(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):
		r = 0
		for k in range(H):
			if i >> k & 1:
				for l in range(W):
					if j >> l & 1:
						if c[k][l] == '#':
							r += 1
		if r == K:
			ans += 1
print(ans)


import numpy as np
(H, W, K) = list(map(int, input().split()))
C = np.zeros((H, W))
for i in range(H):
	c = input()
	for j in range(len(c)):
		if c[j] == '#':
			C[i][j] = 1
CH = []
CW = []
for i in range(2 ** H):
	cl = []
	for j in range(H):
		if bin(i)[-j - 1] == '1':
			cl.append(j)
		elif bin(i)[-j - 1] == 'b':
			break
	CH.append(cl)
for i in range(2 ** W):
	cl = []
	for j in range(W):
		if bin(i)[-j - 1] == '1':
			cl.append(j)
		elif bin(i)[-j - 1] == 'b':
			break
	CW.append(cl)
ans = 0
for i in range(len(CH)):
	for j in range(len(CW)):
		count = 0
		for k in range(len(CH[i])):
			for l in range(len(CW[j])):
				count += C[CH[i][k]][CW[j][l]]
		if count == K:
			ans += 1
print(ans)


(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):
		cnt = 0
		for p in range(h):
			for q in range(w):
				if i & 1 << p and j & 1 << q:
					if c[p][q] == '#':
						cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(n, m, k) = map(int, input().split())
arr = []
for _ in range(n):
	arr.append(list(input()))
ans = 0
for i in range(1 << n):
	for j in range(1 << m):
		black = 0
		for q in range(n):
			for r in range(m):
				if i & 1 << q and j & 1 << r and (arr[q][r] == '#'):
					black += 1
		if black == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0
for h in range(2 ** H):
	for w in range(2 ** W):
		cnt = 0
		for i in range(H):
			for j in range(W):
				if h >> i & 1:
					continue
				if w >> j & 1:
					continue
				if S[i][j] == '#':
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from itertools import product

def main():
	(h, w, k) = list(map(int, input().split()))
	gg = []
	for _ in range(h):
		row = [1 if c == '#' else 0 for c in list(input())]
		gg.extend(row)
	row_pro = tuple(product((0, 1), repeat=h))
	col_pro = tuple(product((0, 1), repeat=w))
	rows = []
	for re in row_pro:
		rows.append([i for (i, b) in enumerate(re) if b])
	cols = []
	for ce in col_pro:
		cols.append([i for (i, b) in enumerate(ce) if b])
	pat = tuple(product(rows, cols))
	r = 0
	for pate in pat:
		t0 = 0
		for p0 in pate[0]:
			for p1 in pate[1]:
				t0 += gg[p0 * w + p1]
		if t0 == k:
			r += 1
	print(r)

def __starting_point():
	main()
__starting_point()


(h, w, k) = map(int, input().split())
c = [list(input()) for _ in range(h)]
res = 0
for i in range(1 << h):
	for j in range(1 << w):
		cnt = 0
		for a in range(h):
			for b in range(w):
				if not (i >> a & 1 or j >> b & 1) and c[a][b] == '#':
					cnt += 1
		if cnt == k:
			res += 1
print(res)


(h, w, k) = map(int, input().split())
mat = [input() for _ in range(h)]
ans = 0
for row in range(2 ** h):
	for col in range(2 ** w):
		bs = 0
		for r in range(h):
			for c in range(w):
				if mat[r][c] == '#' and row >> r & 1 == 0 and (col >> c & 1 == 0):
					bs += 1
		if bs == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
S = [list(input()) for _ in range(H)]
ans = 0
for H_mask in range(2 ** H):
	for W_mask in range(2 ** W):
		cnt = 0
		for i in range(H):
			for j in range(W):
				if H_mask >> i & 1 == 0 and W_mask >> j & 1 == 0 and (S[i][j] == '#'):
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
grid = [input() for _ in range(H)]
ans = 0
for mh in range(1 << H):
	for mw in range(1 << W):
		count = 0
		for h in range(H):
			for w in range(W):
				if mh >> h & 1 == 0 and mw >> w & 1 == 0 and (grid[h][w] == '#'):
					count += 1
		if count == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
C = []
for _ in range(H):
	C.append(input())
A = 2 ** W
B = 2 ** H
M = 0
for a in range(A):
	for b in range(B):
		X = 0
		for y in range(H):
			for x in range(W):
				if (a >> x) % 2 == 1 and (b >> y) % 2 == 1 and (C[y][x] == '#'):
					X += 1
		if X == K:
			M += 1
print(M)


(h, w, k) = map(int, input().split())
c = []
black = 0
for _ in range(h):
	tmp = input()
	black += tmp.count('#')
	c.append(tmp)
cnt = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		bl = black
		for ii in range(h):
			for jj in range(w):
				if i & 1 << ii or j & 1 << jj:
					if c[ii][jj] == '#':
						bl -= 1
		if bl == k:
			cnt += 1
print(cnt)


(H, W, K) = map(int, input().split())
a = [input() for i in range(H)]
ans = 0
for i in range(1 << H):
	for j in range(1 << W):
		black = 0
		for k in range(H):
			for l in range(W):
				if i >> k & 1 == 0 and j >> l & 1 == 0 and (a[k][l] == '#'):
					black += 1
		if black == K:
			ans += 1
print(ans)


from collections import Counter
import math
import statistics
import itertools
(H, W, K) = list(map(int, input().split()))
two = [list(input()) for _ in range(H)]
ans = 0
for i in range(2 ** H):
	for j in range(2 ** W):
		count = 0
		for h in range(H):
			for w in range(W):
				if i >> h & 1 == 1 and j >> w & 1 == 1:
					if two[h][w] == '#':
						count += 1
		if count == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
grid = [input() for _ in range(h)]
n = h + w
ans = 0
for bit in range(1 << n):
	cnt = 0
	for i in range(h):
		for j in range(w):
			if bit >> i & 1:
				if bit >> h + j & 1:
					if grid[i][j] == '#':
						cnt += 1
	if cnt == k:
		ans += 1
print(ans)


(h, w, K) = map(int, input().split())
G = [list(input()) for _ in range(h)]
count = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		tmp = 0
		for k in range(h):
			for m in range(w):
				if not i >> k & 1 and (not j >> m & 1) and (G[k][m] == '#'):
					tmp += 1
		if tmp == K:
			count += 1
print(count)


from itertools import product
(h, w, k) = list(map(int, input().split()))
table = [list(input()) for _ in range(h)]
ans = 0
for row_bit in product(list(range(2)), repeat=h):
	for col_bit in product(list(range(2)), repeat=w):
		tmp = 0
		for row in range(h):
			for col in range(w):
				if table[row][col] == '#' and (row_bit[row] and col_bit[col]):
					tmp += 1
		if tmp == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
s = [input() for _ in range(h)]
ans = 0
for ib in range(1 << h):
	for jb in range(1 << w):
		cc = 0
		for i in range(h):
			if ib & 1 << i:
				continue
			for j in range(w):
				if jb & 1 << j:
					continue
				cc += s[i][j] == '#'
		if cc == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
C = [list(input()) for _ in range(H)]
ans = 0
for row in range(2 ** H - 1):
	for col in range(2 ** W - 1):
		count = 0
		for i in range(H):
			for j in range(W):
				if not row >> i & 1 and (not col >> j & 1) and (C[i][j] == '#'):
					count += 1
		if count == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
C = [input() for _ in range(H)]
ans = 0
for h in range(2 ** H):
	for w in range(2 ** W):
		black = 0
		for i in range(H):
			for j in range(W):
				if h >> i & 1 == 0 and w >> j & 1 == 0 and (C[i][j] == '#'):
					black += 1
		if black == K:
			ans += 1
print(ans)


(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):
		cnt = 0
		for ii in range(h):
			if i >> ii & 1:
				for jj in range(w):
					if j >> jj & 1:
						cnt += c[ii][jj] == '#'
		ans += cnt == k
print(ans)


(h, w, x) = map(int, input().split())
c = [input() for _ in [0] * h]
print(sum((x == sum((i >> k & 1 and j >> l & 1 and (c[k][l] == '#') for k in range(h) for l in range(w))) for i in range(2 ** h) for j in range(2 ** w))))


from itertools import product
(h, w, k) = map(int, input().split())
c = [[1 if j == '#' else 0 for j in input()] for i in range(h)]
cnt = 0
for br in product([0, 1], repeat=h):
	for bc in product([0, 1], repeat=w):
		if sum((c[i][j] * br[i] * bc[j] for (i, j) in product(range(h), range(w)))) == k:
			cnt += 1
print(cnt)


(H, W, K) = map(int, input().split())
li = [input() for _ in range(H)]
ans = 0
for ir in range(1 << H):
	for jr in range(1 << W):
		cnt = 0
		for i in range(H):
			if ir >> i & 1:
				continue
			for j in range(W):
				if jr >> j & 1:
					continue
				cnt += li[i][j] == '#'
		if cnt == K:
			ans += 1
print(ans)


import itertools
(H, W, K) = map(int, input().split())
c = [input() for _ in range(H)]
ans = 0
for i in range(H + 1):
	for j in range(W + 1):
		for row in itertools.combinations([x for x in range(H)], i):
			for column in itertools.combinations([x for x in range(W)], j):
				tmp = 0
				for tr in range(H):
					for tc in range(W):
						if tr in row:
							continue
						if tc in column:
							continue
						if c[tr][tc] == '#':
							tmp += 1
				if tmp == K:
					ans += 1
print(ans)


(H, W, K) = list(map(int, input().split()))
Square = [0] * H
for i in range(H):
	C = input()
	Square[i] = C
ans = 0
nowH = [0] * H
nowW = [0] * W
for j in range(2 ** H):
	for p in range(H):
		nowH[p] = j % 2
		j //= 2
	for k in range(2 ** W):
		kouho = 0
		for q in range(W):
			nowW[q] = k % 2
			k //= 2
		for s in range(H):
			for t in range(W):
				if nowH[s] == 0 and nowW[t] == 0 and (Square[s][t] == '#'):
					kouho += 1
		if kouho == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = [list(input()) for _ in range(H)]
ans = 0
for nh in range(2 ** H):
	for nw in range(2 ** W):
		count = 0
		for h in range(H):
			for w in range(W):
				if 2 ** h & nh != 2 ** h and 2 ** w & nw != 2 ** w and (c[h][w] == '#'):
					count += 1
		if count == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
C = list((input() for _ in range(H)))
ans = 0
import itertools
tf = ('Yes', 'No')
l = list(itertools.product(tf, repeat=H + W))
black = 0
for i in range(2 ** (H + W)):
	for j in range(H):
		for k in range(W):
			if l[i][j] == 'No' and l[i][H + k] == 'No' and (C[j][k] == '#'):
				black += 1
	if black == K:
		ans += 1
	black = 0
print(ans)


import sys
input = lambda : sys.stdin.readline().strip()
(h, w, k) = [int(x) for x in input().split()]
g = [input() for _ in range(h)]
ans = 0
for r in range(1 << h):
	for c in range(1 << w):
		if sum((1 for i in range(h) for j in range(w) if r & 1 << i == 0 and c & 1 << j and (g[i][j] == '#'))) == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
C = [input() for _ in range(H)]
ans = 0
for r in range(1 << H):
	for c in range(1 << W):
		k = 0
		for h in range(H):
			if r >> h & 1:
				continue
			for w in range(W):
				if c >> w & 1:
					continue
				if C[h][w] == '#':
					k += 1
		if k == K:
			ans += 1
print(ans)


import sys
(H, W, K) = list(map(int, input().split()))
c = []
for i in range(H):
	c.append(list(input()))
ans = 0
for i in range(2 ** H):
	for j in range(2 ** W):
		count = 0
		for h in range(H):
			for w in range(W):
				if i >> h & 1 & j >> w & 1:
					if c[h][w] == '#':
						count += 1
		if count == K:
			ans += 1
print(ans)


l = input().split(' ')
H = int(l[0])
W = int(l[1])
K = int(l[2])
c = []
retval = 0
for i in range(H):
	c.append(input())
for maski in range(1 << H):
	for maskj in range(1 << W):
		count = 0
		for i in range(H):
			for j in range(W):
				if maski >> i & 1 == 1 and maskj >> j & 1 == 1 and (c[i][j] == '#'):
					count += 1
		if count == K:
			retval += 1
print(retval)


(h, w, k) = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for x2 in range(2 ** (h + w)):
	x = format(x2, 'b')
	x = (h + w - len(x)) * '0' + x
	co = 0
	for i in range(h):
		if x[i] == '0':
			for j in range(w):
				if x[h + j] == '0' and c[i][j] == '#':
					co += 1
	if co == k:
		ans += 1
print(ans)


(h, w, k) = map(int, input().split())
grid = [input() for _ in range(h)]
ans = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		count = 0
		for m in range(h):
			for l in range(w):
				if i >> m & 1 == 0 and j >> l & 1 == 0 and (grid[m][l] == '#'):
					count += 1
		if count == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
arr = [input() for i in range(H)]
ans = 0
for ib in range(1 << H):
	for jb in range(1 << W):
		cnt = 0
		for i in range(H):
			for j in range(W):
				if ib >> i & 1:
					continue
				if jb >> j & 1:
					continue
				if arr[i][j] == '#':
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)


(h, w, kk) = map(int, input().split())
c = []
for i in range(h):
	c.append(input())
cnt = 0
for i in range(2 ** (h + w)):
	total = 0
	for j in range(h):
		if i >> j & 1:
			for k in range(w):
				if i >> h + k & 1 and c[j][k] == '#':
					total += 1
	if total == kk:
		cnt += 1
print(cnt)


(h, w, k) = map(int, input().split(' '))
c = [input() for x in range(h)]
cnt = 0
for m in range(2 ** (h + w)):
	cc = c.copy()
	for ij in range(h + w):
		if m >> ij & 1:
			if ij in range(h):
				cc[ij] = '.' * w
			if ij in range(h, h + w):
				for t in range(h):
					cc[t] = cc[t][:ij - h] + '.' + cc[t][ij + 1 - h:]
	num = sum((cc[s].count('#') for s in range(h)))
	if num == k:
		cnt += 1
print(cnt)


(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] == '#' and bi[i] == '0' and (bi[h + j] == '0'):
				cnt += 1
	if cnt == k:
		ans += 1
print(ans)


def MI():
	return map(int, input().split())
(H, W, K) = MI()
Map = [input() for _ in range(H)]
ans = 0
for gyou in range(1 << H):
	for retsu in range(1 << W):
		count = 0
		for i in range(H):
			for j in range(W):
				if gyou >> i & 1 and retsu >> j & 1:
					if Map[i][j] == '#':
						count += 1
		if count == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = [[i == '#' for i in input()] for _ in range(H)]
ret = 0
for x in range(1 << W):
	for y in range(1 << H):
		s = 0
		for i in range(W):
			for j in range(H):
				if x & 1 << i or y & 1 << j:
					continue
				s += c[j][i]
		if s == K:
			ret += 1
print(ret)


(H, W, K) = map(int, input().split())
C = [input() for _ in range(H)]
ANS = 0
for i in range(1 << W):
	D = [0] * 37
	D[0] = 1
	for c in C:
		cnt = 0
		for b in range(6):
			if i & 1 << b and c[b] == '#':
				cnt += 1
		for j in range(36 - cnt, -1, -1):
			D[j + cnt] += D[j]
	ANS += D[K]
print(ANS)


(H, W, K) = map(int, input().split())
ans = 0
c = [input() for i in range(H)]
for i in range(2 ** H):
	for j in range(2 ** W):
		test = 0
		for k in range(H * W):
			h = k // W
			w = k % W
			if i >> h & 1 == 0 and j >> w & 1 == 0:
				test += c[h][w] == '#'
		ans += test == K
print(ans)


from itertools import product as pd
(h, w, k) = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
for (i, j) in pd(range(1 << h), range(1 << w)):
	temp = 0
	for (x, y) in pd(range(h), range(w)):
		if 1 << x & i and 1 << y & j:
			if c[x][y] == '#':
				temp += 1
	ans += temp == k
print(ans)


(h, w, k) = map(int, input().split())
import sys
c = [[str(a) for a in l.strip()] for l in sys.stdin]
ans = 0
b = 2 ** (h + w)
for i in range(b):
	for j in range(h):
		for q in range(w):
			if i >> j & 1 and i >> q + h & 1:
				if c[j][q] == '#':
					sum += 1
	if sum == k:
		ans += 1
	sum = 0
print(ans)


(h, w, k) = map(int, input().split())
fig = [list(input()) for _ in range(h)]
count = 0
import itertools
for r_paint in itertools.product([0, 1], repeat=h):
	for c_paint in itertools.product([0, 1], repeat=w):
		kuro = 0
		for row in range(h):
			for col in range(w):
				if fig[row][col] == '#' and r_paint[row] == 0 and (c_paint[col] == 0):
					kuro += 1
		if kuro == k:
			count += 1
print(count)


import sys
(h, w, k) = map(int, next(sys.stdin).split())
a = list(sys.stdin)
ans = 0
for y in range(1 << h):
	for x in range(1 << w):
		ct = 0
		for i in range(h):
			if y & 1 << i:
				continue
			for j in range(w):
				if x & 1 << j:
					continue
				ct += a[i][j] == '#'
		ans += ct == k
print(ans)


(h, w, k) = map(int, input().split())
ans = 0
c = [input() for i in range(h)]
for i in range(2 ** h):
	for j in range(2 ** w):
		cnt = 0
		for l in range(h):
			for m in range(w):
				if c[l][m] == '#' and i >> l & 1 and j >> m & 1:
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = []
ans = 0
for i in range(h):
	c_i = list(input())
	c.append(c_i)
for i in range(1 << h):
	for j in range(1 << w):
		cnt = 0
		for ii in range(h):
			for jj in range(w):
				if i >> ii & 1:
					continue
				if j >> jj & 1:
					continue
				if c[ii][jj] == '#':
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


from itertools import combinations
(H, W, K) = map(int, input().split())
C = [input() for _ in range(H)]
ans = 0
for comb_H in [list(combinations(range(H), a)) for a in range(H + 1)]:
	for comb_W in [list(combinations(range(W), a)) for a in range(W + 1)]:
		for tuple_H in comb_H:
			for tuple_W in comb_W:
				tmp = 0
				for i in range(H):
					for j in range(W):
						if i not in tuple_H and j not in tuple_W and (C[i][j] == '#'):
							tmp += 1
				if tmp == K:
					ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [input() for i in range(h)]
ans = 0
for a in range(1 << h):
	for b in range(1 << w):
		cnt = 0
		for i in range(h):
			if a >> i & 1:
				continue
			for j in range(w):
				if b >> j & 1:
					continue
				cnt += c[i][j] == '#'
		ans += cnt == k
print(ans)


(h, w, k) = map(int, input().split())
c = []
for i in range(h):
	y = list(input())
	c.append(y)
s = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		t = 0
		for a in range(h):
			for b in range(w):
				if i // 2 ** a % 2 == 1 and j // 2 ** b % 2 == 1 and (c[a][b] == '#'):
					t += 1
		if t == k:
			s += 1
print(s)


(H, W, K) = map(int, input().split())
c = [list(input()) for i in range(H)]
count = 0
for bit in range(1 << H + W):
	black = 0
	for shift_h in range(H):
		for shift_w in range(W):
			if c[shift_h][shift_w] == '#' and bit >> W + shift_h & 1 and bit >> shift_w & 1:
				black += 1
	if black == K:
		count += 1
print(count)


from itertools import product
(h, w, k) = list(map(int, input().split()))
grid = []
for i in range(h):
	grid.append(input())
pattern = list(product((0, 1), repeat=h + w))
result = 0
for p in range(len(pattern)):
	p_h = pattern[p][:h]
	p_w = pattern[p][h:]
	cnt = 0
	for i in range(h):
		if p_h[i] == 0:
			for j in range(w):
				if p_w[j] == 0:
					now = grid[i][j]
					if now == '#':
						cnt += 1
	if cnt == k:
		result += 1
print(result)


(h, w, k) = map(int, input().split())
ccc = [input() for _ in range(h)]
ans = 0
for bit_h in range(2 ** h):
	for bit_w in range(2 ** w):
		cnt = 0
		for i in range(h):
			for j in range(w):
				if bit_h >> i & 1 == 0 and bit_w >> j & 1 == 0:
					if ccc[i][j] == '#':
						cnt += 1
		if cnt == k:
			ans += 1
print(ans)


(H, W, K) = [int(s) for s in input().split()]
ls = [[] for _ in range(H)]
for i in range(H):
	ls[i] = input()
ans = 0
for i in range(2 ** H):
	for j in range(2 ** W):
		count = 0
		for h in range(H):
			for w in range(W):
				if ls[h][w] == '#':
					if 2 ** h & i == 0 and 2 ** w & j == 0:
						count += 1
		if count == K:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
c = [input() for i in range(h)]
ans = 0
from itertools import product
for i in product(range(2), repeat=h):
	for j in product(range(2), repeat=w):
		temp = 0
		for a in range(h):
			for b in range(w):
				if i[a] == 1 and j[b] == 1 and (c[a][b] == '#'):
					temp += 1
		if temp == k:
			ans += 1
print(ans)


(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):
		black = 0
		for m in range(h):
			for n in range(w):
				if i >> m & 1 == 0 and j >> n & 1 == 0 and (c[m][n] == '#'):
					black += 1
		if black == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
maze = []
for i in range(h):
	s = input()
	maze.append([c for c in s])
ans = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		bla = 0
		for column in range(h):
			for line in range(w):
				if i >> column & 1 and j >> line & 1 and (maze[column][line] == '#'):
					bla += 1
		if bla == k:
			ans += 1
print(ans)


from itertools import product
(h, w, k) = map(int, input().split())
CC = [input() for _ in range(h)]
total = 0
for x in product((0, 1), repeat=w):
	for y in product((0, 1), repeat=h):
		count = 0
		for i in range(h):
			if y[i]:
				continue
			for j in range(w):
				if x[j]:
					continue
				if CC[i][j] == '#':
					count += 1
		if count == k:
			total += 1
print(total)


(h, w, k) = map(int, input().split())
matrix = [list(input()) for n in range(h)]
ans = 0
for fill_h in range(2 ** h):
	for fill_w in range(2 ** w):
		cnt = 0
		for i in range(h):
			for j in range(w):
				if fill_h >> i & 1 == 0 and fill_w >> j & 1 == 0:
					if matrix[i][j] == '#':
						cnt += 1
		if cnt == k:
			ans += 1
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
(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):
		ct = 0
		for ih in range(h):
			for iw in range(w):
				if i & 1 << ih == 0 and j & 1 << iw == 0 and (C[ih][iw] == '#'):
					ct += 1
		if ct == k:
			ans += 1
print(ans)


import itertools
(h, w, k) = map(int, input().split())
c = [input() for i in range(h)]
ans = 0
for i in itertools.product(range(2), repeat=h):
	for j in itertools.product(range(2), repeat=w):
		s = 0
		for x in range(h):
			for y in range(w):
				if c[x][y] == '#' and i[x] and j[y]:
					s += 1
		if s == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
C = []
ans = 0
for i in range(h):
	C.append(input())
for i in range(2 ** h):
	for j in range(2 ** w):
		counts = 0
		for l in range(h):
			for m in range(w):
				if C[l][m] == '#' and i >> l & 1 and j >> m & 1:
					counts += 1
		if counts == k:
			ans += 1
print(ans)


def trans(l):
	return [list(x) for x in list(zip(*l))]
from itertools import product
import copy
(h, w, k) = map(int, input().split())
c = []
for _ in range(h):
	c.append([c for c in input()])
A = [i for i in product([1, 0], repeat=h)]
B = [i for i in product([1, 0], repeat=w)]
ans = 0
for a in A:
	temp1 = copy.copy(c)
	for (i, x) in enumerate(a):
		if x == 1:
			temp1[i] = ['.'] * w
	for b in B:
		temp2 = trans(temp1)
		for (i, x) in enumerate(b):
			if x == 1:
				temp2[i] = ['.'] * h
		cnt = 0
		for t in temp2:
			cnt += t.count('#')
		if cnt == k:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
X = [[1 if a == '#' else 0 for a in input()] for _ in range(H)]
ans = 0
for ii in range(1 << H):
	for jj in range(1 << W):
		if sum([sum([X[i][j] for j in range(W) if jj >> j & 1]) for i in range(H) if ii >> i & 1]) == K:
			ans += 1
print(ans)


from itertools import product
(H, W, K) = map(int, input().split())
c = []
ans = 0
for i in range(H):
	c.append(input())
for row_bit in product(range(2), repeat=H):
	for col_bit in product(range(2), repeat=W):
		count = 0
		for row in range(H):
			for col in range(W):
				if c[row][col] == '#' and (row_bit[row] and col_bit[col]):
					count += 1
		if count == K:
			ans += 1
print(ans)


(H, W, K) = map(int, input().split())
c = [list(input()) for i in range(H)]
ans = 0
for i in range(1 << H):
	mh = []
	for j in range(H):
		if i & 1 << j:
			mh.append(j)
	mh = set(mh)
	for j in range(1 << W):
		mw = []
		for k in range(W):
			if j & 1 << k:
				mw.append(k)
		mw = set(mw)
		count = 0
		for a in range(H):
			for b in range(W):
				if not a in mh and (not b in mw) and (c[a][b] == '#'):
					count += 1
		if count == K:
			ans += 1
print(ans)


(h, w, x) = map(int, input().split())
c = [input() for _ in range(h)]
a = 0
for i in range(2 ** h):
	for j in range(2 ** w):
		t = 0
		for k in range(h):
			for l in range(w):
				if i >> k & 1 and j >> l & 1 and (c[k][l] == '#'):
					t += 1
		if t == x:
			a += 1
print(a)


(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):
		black = 0
		for i in range(H):
			for j in range(W):
				if I >> i & 1 == 0 and J >> j & 1 == 0 and (c[i][j] == '#'):
					black += 1
		if black == K:
			ans += 1
print(ans)


(h, w, k) = list(map(int, input().split()))
c_list = []
for i in range(h):
	c_list.append(list(str(input())))
h_TF_list = []
w_TF_list = []
for i in range(2 ** h):
	p_m_list = [False for i in range(h)]
	for j in range(h):
		if i >> j & 1:
			p_m_list[j] = True
	h_TF_list.append(p_m_list)
for i in range(2 ** w):
	p_m_list = [False for i in range(w)]
	for j in range(w):
		if i >> j & 1:
			p_m_list[j] = True
	w_TF_list.append(p_m_list)
count = 0
for h_list in h_TF_list:
	for w_list in w_TF_list:
		p = 0
		for i in range(h):
			for j in range(w):
				if c_list[i][j] == '#' and h_list[i] == True and (w_list[j] == True):
					p += 1
		if p == k:
			count += 1
print(count)


(h, w, k) = map(int, input().split())
c = []
for i in range(h):
	c.append(input())
ans = 0
for markH in range(2 ** h):
	for markW in range(2 ** w):
		black = 0
		for i in range(h):
			for j in range(w):
				if markH >> i & 1 and markW >> j & 1 and (c[i][j] == '#'):
					black += 1
		if black == k:
			ans += 1
print(ans)


(h, w, k) = map(int, input().split())
s = [list(input()) for i in range(h)]
ans = 0
for i in range(2 ** h - 1):
	for j in range(2 ** w - 1):
		cnt = 0
		for x in range(h):
			for y in range(w):
				if i >> x & 1 == 0 and j >> y & 1 == 0 and (s[x][y] == '#'):
					cnt += 1
		if cnt == k:
			ans += 1
print(ans)


from itertools import product
(H, W, K) = map(int, input().split())
grid = [input() for _ in range(H)]
ans = 0
for (h, w) in product(range(1 << H), range(1 << W)):
	temp = 0
	for i in range(H):
		if h & 1 << i:
			for (j, c) in enumerate(grid[i]):
				if w & 1 << j and c == '#':
					temp += 1
	if temp == K:
		ans += 1
print(ans)


from itertools import groupby, accumulate, product, permutations, combinations
(H, W, K) = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0
for p in product([0, 1], repeat=H + W):
	cnt = 0
	for i in range(H):
		for j in range(W):
			if S[i][j] == '#' and p[i] == 0 and (p[H + j] == 0):
				cnt += 1
	if cnt == K:
		ans += 1
print(ans)


import copy
(H, W, K) = list(map(int, input().split()))
d = {}
ans = 0
for i in range(H):
	d['c' + str(i)] = list(input())

def changeRow(d, num, W):
	d['c' + str(num)] = ['.'] * W

def changeColum(d, num, H):
	for i in range(H):
		d['c' + str(i)][num] = '.'

def checkSharp(d, H):
	cnt = 0
	for i in range(H):
		cnt += d['c' + str(i)].count('#')
	return cnt
for i in range(2 ** W):
	for j in range(2 ** H):
		dCopy = copy.deepcopy(d)
		for k in range(W):
			if i >> k & 1:
				changeColum(dCopy, k, H)
		for k in range(H):
			if j >> k & 1:
				changeRow(dCopy, k, W)
		if K == checkSharp(dCopy, H):
			ans += 1
print(ans)


(H, W, K) = [int(_) for _ in 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):
		count = 0
		for row in range(H):
			for col in range(W):
				if i >> row & 1 and j >> col & 1:
					if C[row][col] == '#':
						count += 1
		if count == K:
			ans += 1
print(ans)