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

Solution (Python):


from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key
from copy import deepcopy as dc

INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    H, W, K = mulinputs()
    cs = []
    for _ in range(H):
        cs.append(input())

    def count(arr):
        _cnt = 0
        for line in arr:
            for ch in line:
                if ch != '
                    continue
                _cnt += 1
        return _cnt

    for i in range((1<<H)-1):
        for j in range((1<<W)-1):
            h, w, _i, _j = [], [], i, j
            while _i > 0:
                h.append(_i%2)
                _i >>= 1
            while _j > 0:
                w.append(_j%2)
                _j >>= 1
            _cs = dc(cs)
            if h:
                for idx, _h in enumerate(h):
                    _cs[idx] = 'r' * W if _h else _cs[idx]
            if w:
                for idx, _w in enumerate(w):
                    if not _w:
                        continue
                    for cidx in range(len(_cs)):
                        tmp = ''
                        for ii, ch in enumerate(_cs[cidx]):
                            tmp += 'r' if ii == idx else ch
                        _cs[cidx] = tmp
            if count(_cs) == K:
                cnt += 1

    
    print(cnt)

Solution (Python):
import sys
from operator import itemgetter
import copy
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    h, w, K = mi()
    c = [list(input().rstrip()) for _ in range(h)]
    count = 0
    for i in range(h):
        for j in range(w):
            if c[i][j] == "
                c[i][j] = 1
                count += 1
            else:
                c[i][j] = 0
    
    ans = 0
    for i in range(1<<h):
        for j in range(1<<w):
            tmp = copy.deepcopy(c)
            for k in range(h):
                if i>>k & 1:
                    for l in range(w):
                        tmp[k][l] = 0
            for k in range(w):
                if j>>k & 1:
                    for l in range(h):
                        tmp[l][k] = 0
            s = 0
            for t in tmp:
                s += sum(t)
            if s == K:
                ans += 1

    print(ans)

    return

main()

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


def main():
    h, w, k = map(int, input().split())
    grid = np.full((h, w), False, dtype=bool)
    for i in range(h):
        line = input()
        for j in range(w):
            if line[j] == '
                grid[i][j] = True
    ans = 0
    for e in product((True, False), repeat=h + w):
        grid_copy = np.copy(grid)
        for i in range(h):
            if e[i]:
                grid_copy[i, :] = False
        for j in range(w):
            if e[h + j]:
                grid_copy[:, j] = False
        if np.sum(grid_copy) == k:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import collections

    h,w,k = map(int,input().split())
    c = []
    total = 0
    for i in range(h):
        cc = list(input())
        c.append(cc)
        total += collections.Counter(cc)['
    from itertools import combinations
    r = list(range(0,h))
    col = list(range(0,w))
    
    
    ans = 0

    for i in range(h+1):
        for row in list(combinations(r, i)):
            rcnt = collections.Counter(row)
            for j in range(w+1):
                for co in list(combinations(col, j)):
                    ccnt = collections.Counter(co)

                    sumr = 0
                    for kk in row:
                        for l in c[kk]:
                            if l == '
                                sumr+=1

                    for kk in co:
                        for l in range(h):
                            if c[l][kk] == '
                                sumr+=1
                    
                    if total - sumr == k:
                        ans += 1
    print(ans)
if __name__=='__main__':
    main()

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

Solution (Python):

h,w,k = list(map(int,input().split()))
c = [list(input()) for _ in range(h)]
black_total  = 0
row_black_cnt = []
col_black_cnt = []
for ci in c:
    row_black_cnt.append(ci.count("
    black_total+=ci.count("

for cj in zip(*c):
    col_black_cnt.append(cj.count("

cc = []
for i in c:
    tmp = []
    for j in i:
        if j =="
            tmp.append(1)
        else:
            tmp.append(0)
    cc.append(tmp)
from itertools import product
row_itrt = list(product([0,1],repeat=h))
col_itrt = list(product([0,1],repeat=w))

ret = 0
for row_ptn in row_itrt:
    row_ptn = [i for i,v in enumerate(row_ptn) if v==1]
    for col_ptn in col_itrt:
        cnt = black_total
        col_ptn = [i for i,v in enumerate(col_ptn) if v==1]
        for r in row_ptn:
            for c in col_ptn:
                cnt += cc[r][c]
        for r in row_ptn:
            cnt -= row_black_cnt[r]
        for c in col_ptn:
            cnt -= col_black_cnt[c]
        if cnt==k:
            ret+=1

print(ret)

Solution (Python):
from copy import deepcopy

h,w,K=map(int,input().split())
lst=[]
for i in range(h):
    c=list(input())
    lst.append(c)
ans=0
for i in range(2**(h+w)):
    nuri=[[],[]]
    count_h=0
    count_w=0
    for j in range(h+w):
        if ((i>>j)&1):
            if j<h:
                nuri[0].append(j)
                count_h+=1
            else:
                nuri[1].append(j-h)
                count_w+=1
    c_lst=deepcopy(lst)
    for j in range(count_h):
        for k in range(w):
            if c_lst[nuri[0][j]][k]=="
                c_lst[nuri[0][j]][k]="."
    for j in range(count_w):
        for k in range(h):
            if c_lst[k][nuri[1][j]]=="
                c_lst[k][nuri[1][j]]="."
    num_shapu=0
    for j in c_lst:
        for k in j:
            if k=="
                num_shapu+=1
    if num_shapu==K:
        ans+=1
print(ans)

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

x = [i.count('
y = [[i[j] for i in c].count('
z = sum(x)
r = 0
for i in range(2**h):
    s = []
    num = i
    for _i in range(h):
        if num%2==1:
            s.append(_i)
        num >>= 1
    for j in range(2**w):
        num = j
        t = []
        for _j in range(w):
            if num%2==1:
                t.append(_j)
            num >>= 1
        if s==[] and t==[]:
            if k == z:
                r += 1
        elif s == []:
            counter = sum(y[n] for n in t)
            if z-counter == k:
                r += 1
        elif t == []:
            counter = sum(x[n] for n in s)
            if z-counter == k:
                r += 1
        else:
            counter = sum(x[n] for n in s) + sum(y[m] for m in t)
            for nn in s:
                for mm in t:
                    if c[nn][mm] == '
                        counter -= 1
            if z-counter == k:
                r += 1

print(r)

Solution (Python):
import sys

H, W, K = map(int, sys.stdin.readline().strip().split())
grid = []
for _ in range(H):
    grid.append(list(sys.stdin.readline().strip()))


ans = 0
for i in range(2**H):
    for j in range(2**W):
        tmp = 0
        for y in range(H):
            for x in range(W):
                if ((j >> x) & 1) or ((i >> y) & 1):
                    
                    continue
                
                
                if grid[y][x] == "
                    tmp += 1
        
        if tmp == K:
            
            ans += 1

print(ans)

Solution (Python):
import numpy as np
import itertools


hwk = input().split(' ')

h = int(hwk[0])
w = int(hwk[1])
k = int(hwk[2])

mat = np.zeros([h, w])

for i in range(h):
  tmp_row_str = input()
  tmp_row = np.array([1 if tmp_row_str[j] == '
  mat[i] = tmp_row

count = 0

sum_rows = mat.sum(axis=0)
sum_cols = mat.sum(axis=1)

sum_total = mat.sum()

row_combs = itertools.product([0, 1], repeat=h)
col_combs = list(itertools.product([0, 1], repeat=w))

count = 0


for row_comb in row_combs:
  
  for col_comb in col_combs:
    tmp_mat = mat.copy()
    tmp_mat[np.array(row_comb).astype('bool')] = 0
    tmp_mat[:, np.array(col_comb).astype('bool')] = 0

    
    if tmp_mat.sum() == k:
      count += 1

print(count)

"""
while True:
  if sum_total == k:
    print(1)
    break
  
"""

Solution (Python):
import sys
import numpy as np

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

H, W, K = map(int, sys.stdin.readline().rstrip().split())
C = []
for _ in range(H):
    C.append([0 if s == "." else 1 for s in sys.stdin.readline().rstrip()])

A = np.array(C)


ans = 0
for i in range(2**H):
    for j in range(2**W):
        A = np.array(C)

        for row in range(H):
            if (i >> row) & 1 == 1:
                A[row, :] = 0

        for col in range(W):
            if (j >> col) & 1 == 1:
                A[:, col] = 0

        
        

        if A.sum() == K:
            ans += 1

print(ans)

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

ans = 0

def cnt(a, h, w):
    global ans
    ret = 0
    for i,s in enumerate(a):
        if h[i]!=0:
            continue
        for j,c in enumerate(s):
            if w[j] !=0:
                continue
            ret += 1 if c == "
    if K == ret:
        ans += 1

def hf(h):
    if len(h) == H:
        wf(h,[])
        return
    hf(h+[0])
    hf(h+[1])

def wf(h,w):
    if len(w) == W:
        cnt(c, h, w)
        return
    wf(h, w+[0])
    wf(h, w+[1])

hf([])
print(ans)

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

c = [[] for _ in range(H)]
s = [[] for _ in range(H)]
t = [[] for _ in range(W)]

for i in range(H):
    c[i] = input()
for i in range(H):
    s[i] = c[i].count("

num_total = 0

for j in range(W):
    t[j] = 0
    for i in range(H):
        if c[i][j] == "
            t[j] += 1
            num_total += 1


ans = 0
for i in range(2**len(s)):
    num0 = 0
    for j in range(len(s)):
        if ((i >> j) & 1):
            num0 += s[j]
    for k in range(2**len(t)):
        num = num0
        for l in range(len(t)):
            if ((k >> l) & 1):
                num += t[l]
                for j in range(len(s)):
                    if ((i >> j) & 1):
                        if c[j][l] == "
                            num -= 1
        if num_total - num == K:
            ans += 1

print(ans)

Solution (Python):
H, W, K = map(int, input().split())
C = [[0 for i in range(W)] for j in range(H)]
for j in range(H):
  c = input()
  for i in range(W):
    if c[i] == "
      C[j][i] = 1
ans = 0
P = [0 for k in range(H + W)]

while 1:
  S = 0
  for j in range(H):
    for i in range(W):
      if P[j] == 0 and P[H + i] == 0:
        S += C[j][i]
  if S == K:
    ans += 1
  if sum(P) == H + W:
    break
  a = 1
  for k in range(H+W):
    b = (P[k] + a) // 2
    P[k] = (P[k] + a) % 2
    a = b
print(ans)

Solution (Python):


import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W, K = map(int, readline().split())
C = np.array([list(readline().decode().rstrip()) for _ in range(H)])

ans = 0
for bit_h in range(1, 1 << H):
    b_h = [i for i in range(H) if bit_h & (1 << i)]

    for bit_w in range(1, 1 << W):
        b_w = [i for i in range(W) if bit_w & (1 << i)]
        acc = (C[b_h][:, b_w] == "
        if acc == K:
            ans += 1
print(ans)

Solution (Python):
import itertools

data = [0, 1]

h, w, k = map(int, input().split())
countA = 0
gyoL = [0]*h  
retuL = [0]*w  
cL = []
for i in range(h):
    inputL = list(input())
    countSum = 0
    for l in range(w):
        if inputL[l] == "
            countA+=1
            countSum += 1
            retuL[l] += 1
    gyoL[i] = countSum
    cL.append(inputL)

gyo = list(itertools.product(data, repeat=h))
retu = list(itertools.product(data, repeat=w))

ansC = 0
for tG in gyo:
    for tR in retu:
        count = countA
        gOneL = []
        rOneL = []
        for index1 in range(len(tG)):
            if tG[index1] == 1:
                count-=gyoL[index1]
                gOneL.append(index1)
        for index2 in range(len(tR)):
            if tR[index2] == 1:
                count-=retuL[index2]
                rOneL.append(index2)
        for g in gOneL:
            for r in rOneL:
                if cL[g][r] == "
                    count += 1
        if count == k:
            ansC+=1
print(ansC)

Solution (Python):

import numpy as np
from itertools import combinations as comb
h, w, k = map(int, input().split())
a = np.array([list(input()) for _ in [None]*h])
cnt = 0
for j1 in range(h):
    for i1 in comb(range(h), j1):
        for j2 in range(w):
            for i2 in comb(range(w), j2):
                c = np.copy(a)
                c = np.delete(c, list(i1), 0)
                c = np.delete(c, list(i2), 1)
                cnt += np.count_nonzero(c == '
print(cnt)

Solution (Python):
aa=input("").split(" ")
a=[]
for i in range(3):
    a+=[int(aa[i])]
    
    
b=[]
for i in range(a[0]):
    b+=[input("")]
c=[]
for i in range(a[0]):
    d=[]
    for k in b[i]:
        if (k=="."):
            d+=[0]
        else:
            d+=[1]
    c+=[d]
def count(n,m):
    s=0
    for i in range(a[0]):
        for k in range(a[1]):
            if (c[i][k]==1 and n[i]==1 and m[k]==1):
                s+=1
    return s
ss=0
for ii in range(2**a[0]):
    for kk in range(2**a[1]):
        d=ii
        e=kk
        n=[]
        m=[]
        for iii in range(a[0]):
            n+=[d%2]
            d=int((d/2))
        for kkk in range(a[1]):
            m+=[e%2]
            e=int(e/2)
        if (count(n,m)==a[2]):
            ss+=1
print(ss)

Solution (Python):
h,w,K = map(int,input().split())
c = [input() for _ in range(h)]
count = 0

for i in range(2 ** (h+w)):
    ans = 0
    a,b = [],[]
    for j in range(h+w):
        if ((i >> j) & 1):
            if j < h:
                a.append(j)
            else:
                b.append(j-h)
    for k in range(h):
        for l in range(w):
            if c[k][l] == '
                ans += 1
    if ans == K:
        count += 1
print(count)

Solution (Python):
H, W, K = map(int, input().split())
c = []
for _ in range(H):
    c.append(input())
ans = 0
for i in range(2**H):
    bin_i = format(i, f'0{H}b')
    for j in range(2**W):
        bin_j = format(j, f'0{W}b')
        count = 0
        for ii in range(H):
            if bin_i[ii] == '1':
                continue
            for jj in range(W):
                if bin_j[jj] == '1':
                    continue
                if c[ii][jj] == '
                    count+=1
        if count == K:
            ans+=1
print(ans)

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

n=h + w
b=[]
for s in range(2**n):
    a=[1 if s >> i &1 else 0 for i in range(n)] 
    b.append(a)

from copy import deepcopy
count = 0

for part_b in b:
    m =0
    d = deepcopy(c)
    row = part_b[:h]
    col = part_b[h:]
    for i in range(len(row)):
        flg = row[i]
        if flg:
            d[i] = ["赤" for _ in range(w)]
    
    for i in range(len(col)):
        flg = col[i]
        if flg:
            for j in range(h):
        
                d[j][i]= "赤"
                
    for i in range(h):
        for j in range(w):
            if d[i][j] == "
                m +=1
    if m==k:
        count +=1
print(count)

Solution (Python):
import sys






def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))




def main():
	h,w,k=MI()
	G=[]
	for _ in range(h):
		G.append(list(input()))
	
	ans=0

	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&1<<ii and j&1<<jj and G[ii-1][jj-1]=="
						
						cnt+=1
			if cnt==k:
				ans+=1
	print(ans)







if __name__ == "__main__":
	main()

Solution (Python):
H,W,K=map(int, input().split())
C = [ "" for _ in range(H) ]
cx = [ 0 for _ in range(H) ]
cy = [ 0 for _ in range(W) ]
for i in range(H):
  C[i] = input()
  for j in range(W):
    if C[i][j] == "
      cx[i] |= 1 << j
ans = 0
for y in range( 1<<H ):
  for x in range( 1<<W ):
    total = 0
    for i in range(H):
      if ( (y & (1<<i)) != 0 ):
        for j in range(W):
          if ((cx[i] & x) & (1<<j)) != 0:
            total += 1
    if total == K:
      ans += 1
print(ans)

Solution (Python):
"""
AtCoder :: Beginner Contest 173 :: H and V
https://atcoder.jp/contests/abc173/tasks/abc173_c
"""
import sys
from itertools import chain, combinations


def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


def main():
    """Main program."""
    height, width, target = (int(i) for i in sys.stdin.readline().split())
    grid = [[0 for _ in range(width)] for _ in range(height)]
    total_black = 0
    for row in range(height):
        for col, color in enumerate(sys.stdin.readline().strip()):
            if color == '
                grid[row][col] = 1
                total_black += 1

    soln = 0
    for rows_selected in powerset(range(height)):
        for cols_selected in powerset(range(width)):
            if len(cols_selected) == width:
                continue

            selected_black = 0
            for row in rows_selected:
                selected_black += sum(grid[row])

            for col in cols_selected:
                for row in range(height):
                    if row not in rows_selected:
                        selected_black += grid[row][col] 

            if total_black - selected_black == target:
                soln += 1
    print(soln)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))

def main():
    h, w, k = MII()
    cc = [IS() for _ in range(h)]
    all_blacks = 0
    for c in cc:
        all_blacks += sum(1 for s in c if s == '
    cnt = 0
    for hbit in range(1<<h):
        blacks = all_blacks
        hb = []
        
        for i in range(h):
            if hbit & (1<<i):
                hb.append(i)
        
        for hbi in hb:
            blacks -= sum([1 for s in cc[hbi] if s == '
        
        if blacks < k:
            continue

        
        for wbit in range(1<<w):
            wb = []
            for i in range(w):
                if wbit & (1<<i):
                    wb.append(i)
            
            wblack = 0
            for wbi in wb:
                for i in range(h):
                    
                    if i in hb:
                        continue
                    if cc[i][wbi] == '
                        wblack += 1
            if blacks - wblack == k:
                cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W, K = mapint()

rows = [0]*H
query = []
allcnt = 0
for h in range(H):
    Cs = list(input())
    query.append(Cs)
    cnt = sum([1 if i=='
    rows[h] = cnt
    allcnt += cnt
ans = 0
for i in range(1<<H):
    skip = set()
    num = 0
    for h in range(H):
        if (i>>h)&1:
            skip.add(h)
            num += rows[h]
    for j in range(1<<W):
        num2 = num
        for w in range(W):
            if (j>>w)&1:
                for h2 in range(H):
                    if h2 in skip:
                        continue
                    if query[h2][w]=='
                        num2 += 1
        if allcnt-num2==K:
            ans += 1
print(ans)

Solution (Python):
import sys
import numpy as np

def input():
    return sys.stdin.readline()[:-1]

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

def bin_list(num, keta):
    return [i for i, x in enumerate(map(int, format(num, f'0{keta}b'))) if x==1]

cnt = 0
for row in range(2**h):
    for col in range(2**w):
        tmp = np.array(s_li)
        tmp[bin_list(row, h),:] = '.'
        tmp[:,bin_list(col, w)] = '.'
        if np.count_nonzero(tmp=='
            cnt += 1
print(cnt)

Solution (Python):
def main():
    from itertools import combinations
    from copy import deepcopy

    h, w, k = map(int, input().split())
    m = [list(input()) for _ in range(h)]
    c = (sum(m,[])).count('
    cnt = 0
    for i in range(w + 1):
        for w_ in combinations(list(range(w)), i):
            for j in range(h + 1):
                for h_ in combinations(list(range(h)), j):
                    m_ = deepcopy(m)
                    tmp = c
                    for x in w_:
                        for p in range(h):
                            if m_[p][x] == '
                                tmp -= 1
                    for y in h_:
                        for p in range(w):
                            if m_[y][p] == '
                                tmp -= 1
                    for x in w_:
                        for y in h_:
                            if m_[y][x] == '
                                tmp += 1

                    if tmp == k:
                        cnt += 1

    print(cnt)



if __name__ == '__main__':
    main()

Solution (Python):
import itertools, copy

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

c = []

for _ in range(h):
    c.append(list(input()))

ans = 0

iter_h_list = list(itertools.product([0,1], repeat=h))
iter_w_list = list(itertools.product([0,1], repeat=w))

for iter_h in iter_h_list:
    for iter_w in iter_w_list:
        temp_c = copy.deepcopy(c)

        for i in range(h):
            if iter_h[i] == 1:
                temp_c[i] = ["r" for x in temp_c[i]]

        for j in range(w):
            for i in range(h):
                if iter_w[j] == 1:
                    temp_c[i][j] = "r"

        sum_of_shape = [x.count("
        if sum(sum_of_shape) == k:
            ans += 1

print(ans)

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

"""
for i in range(h):
    print(C[i])
"""

def count(C):
    ans = 0
    for i in range(h):
        for j in range(w):
            
            
            if C[i][j] == "
                ans += 1
    return ans



def rewrite(C, h_pat, w_pat):
    ans = deepcopy(C)
    for i, is_write in enumerate(h_pat):
        if is_write == True:
            for j in range(w):
                ans[i][j] = 0
    for j, is_write in enumerate(w_pat):
        if is_write == True:
            for i in range(h):
                ans[i][j] = 0
    return ans

counter = 0
for h_pat in product([0, 1], repeat=h):
    for w_pat in product([0, 1], repeat=w):
        r = rewrite(C, h_pat, w_pat)
        if count(r) == k:
           counter += 1
print(counter)