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



Sample input:
2 3 2
..#
###


Sample output:
5

Submission status: Accepted

Solution code:
# coding: utf-8

from copy import deepcopy


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

    ans = 0

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

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

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

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

    return ans


print(main())

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

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


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

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("out.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# @lru_cache(None)

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

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

Submission status: Accepted

Solution code:
import itertools
import copy
from collections import deque
import heapq
h,w,k = map(int,input().split())
c = [list(input()) for i in range(h)]
#print(c)
ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        ans_check = 0
        h_c = {}
        w_c = {}
        for check in range(h):
            if ((i >> check) & 1):
                h_c[check] = 0
        for check in range(w):
            if ((j >> check) & 1):
                w_c[check] = 0
        #print(h_c,w_c)
        for hc,n in enumerate(c):
            if not hc in h_c:
                continue
            for wc,m in enumerate(n):
                if not wc in w_c:
                    continue
                if m == "#":
                    ans_check += 1
        #print(ans_check)
        if ans_check == k:
            ans += 1
print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

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

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

    print(ans)
        




if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

        if black_cnt == k:
            res += 1

print(res)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

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

print(ans)

Submission status: Accepted

Solution code:
def main():

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

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


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

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

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

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

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

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




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

Submission status: Accepted

Solution code:
import sys
import itertools
import copy

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

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


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

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

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

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

            if count == K:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    print(ans)
                        



if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

import itertools

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

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

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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


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

print(ans)

Submission status: Accepted

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

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

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

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


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

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

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

print(ans)

Submission status: Accepted

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

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


#縦の全探索

ans=0

#print(c)

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

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

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

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

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

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

Submission status: Accepted

Solution code:
from copy import deepcopy
from itertools import product
import numpy as np

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

Submission status: Accepted

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

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

Submission status: Accepted

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

pos = []

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


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

allPoints = 0

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

print(allPoints)

Submission status: Accepted

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

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

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

ans=0
s = sum(row)

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

Submission status: Accepted

Solution code:
from itertools import product
import copy

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

# print(b_cnt)

pattern = 2
# ite_h = product(range(pattern),repeat=h)
# ite_w = product(range(pattern),repeat=w)
ite = product(range(pattern),repeat=h+w)
ans = 0

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

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

    if b_cnt-cnt == k:
        ans += 1
    # print()
    # print(it_h, it_w)
    # print(curr_cl)
    # print(cnt)

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

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

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

print(res)

Submission status: Accepted

Solution code:
from itertools import product

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

for i in range(h):
    for j in range(w):
        if C[i][j] == "#":
            C[i][j] = 1
        else:
            C[i][j] = 0

H_total = [sum(x) for x in C]
W_total = []
for i in range(w):
    total = 0
    for j in range(h):
        total += C[j][i]
    W_total.append(total)

all_black = sum(H_total)

ans = 0

for a in product([0,1], repeat=h):
    for b in product([0,1], repeat=w):
        neg = 0
        for i in range(h):
            if a[i] == 1:
                neg += H_total[i]

        for j in range(w):
            if b[j] == 1:
                neg += W_total[j]

        for i in range(h):
            for j in range(w):
                if a[i]==1 and b[j]==1 and C[i][j]==1:
                    neg -= 1

        if all_black - neg == k:
            ans += 1

print(ans)

Submission status: Accepted

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

c_ = copy.deepcopy(c)
ans = 0
for a in range(2 ** h):
  for b in range(2 ** w):
    for i in range(h):
      if (a >> i) & 1 != 0:
        for j in range(w):
          c[i][j] = '*'
    for j in range(w):
      if (b >> j) & 1 != 0:
        for i in range(h):
          c[i][j] = '*'

    # print(c)
    cnt = 0
    for l in c:
      cnt += l.count('#')
    if cnt == k:
      ans += 1

    c = copy.deepcopy(c_)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


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

    sol = 0

    for i in range(2 ** h):
        for j in range(2 ** w):

            count = 0

            for x in range(h):
                for y in range(w):
                    if c[x][y] == '#' and i & (1 << x) == 0 and j & (1 << y) == 0:
                        count += 1

            if count == k:
                sol += 1

    print(sol)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import itertools
import copy

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    h,w,k=map(int, readline().rstrip().split())
    masu=[""]*h
    for i in range(h):
        masu[i]=readline().rstrip() #.split()

    ans=0
    for x in itertools.product([0,1], repeat=(h+w)):
        m=copy.deepcopy(masu)
        kuro=0
        for i in range(h):
            if x[i]==1:
                m[i]=" "*w
        for i in range(w):
            if x[i+h]==1:
                continue
            for j in range(h):
                if m[j][i]=="#":
                    kuro+=1
        if kuro==k:
            ans+=1
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
C=[list(input()) for i in range(H)]
ans=0
M=0
for i in range(H):
    for j in range(W):
        if C[i][j]=='#':
            M+=1
for i in range(pow(2,H)):
    s=0
    h=[False]*H
    for k in range(H):
        if i>>k & 1:
            h[k]=True
            for x in range(W):
                if C[k][x]=='#':
                    s+=1   
    for j in range(pow(2,W)):
        s_temp=s
        for k in range(W):
            if j>>k & 1:
                for x in range(H):
                    if C[x][k]=='#' and not h[x]:
                        s_temp+=1
        if M-s_temp==K:
            ans+=1
print(ans)