# abc173_c.py
# https://atcoder.jp/contests/abc173/tasks/abc173_c
# C - H and V /
# 実行時間制限: 1 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# H行 W 列に並ぶマスからなるマス目があります。
# 上から i 行目、左から j 列目 (1≤i≤H,1≤j≤W) のマスの色は文字 ci,j として与えられ、ci,jが . のとき白、# のとき黒です。

# 次の操作を行うことを考えます。
# 行を何行か選び (0行でもよい)、列を何列か選ぶ (0列でもよい)。
# そして、選んだ行に含まれるマスと、選んだ列に含まれるマスをすべて赤く塗る。

# 正の整数 Kが与えられます。操作後に黒いマスがちょうど K個残るような行と列の選び方は何通りでしょうか。
# ここで、二つの選び方は、一方においてのみ選ばれる行または列が存在するときに異なるとみなされます。

# 制約
#     1≤H,W≤6
#     1≤K≤HW
#     ci,jは . または #

# 入力
# 入力は以下の形式で標準入力から与えられる。
# H W K
# c1,1c1,2...c1,W
# c2,1c2,2...c2,W
# :
# cH,1cH,2...cH,W

# 出力
# 条件を満たす行と列の選び方の個数を表す整数を出力せよ。

# 入力例 1
# 2 3 2
# ..#
# ###

# 出力例 1
# 5

# 以下の 5通りの選び方が条件を満たします。
#     1行目、1列目
#     1行目、2列目
#     1行目、3列目
#     1列目、2列目
#     3列目

# 入力例 2
# 2 3 4
# ..#
# ###

# 出力例 2
# 1

# 何も選ばないという 1通りの選び方が条件を満たします。

# 入力例 3
# 2 2 3
# ##
# ##

# 出力例 3
# 0

# 入力例 4
# 6 6 8
# ..##..
# .#..#.
# #....#
# ######
# #....#
# #....#

# 出力例 4
# 208


# 解答
def abc173_c(lines):
    H, W, K = map(int, lines[0].split(' '))
    pattern_h = get_pattern(H)
    pattern_w = get_pattern(W)
    answers = 0
    for h in pattern_h:
        for w in pattern_w:
            tmp = list()
            for i in range(1, len(lines)):
                tmp.append(lines[i])
            # 行単位の指定時は行全体を指定
            for n_row in range(H):
                if h[n_row] == '1':
                    tmp[n_row] = '*' * W
            for n_col in range(W):
                if w[n_col] == '1':
                    for n_row in range(H):
                        tmp[n_row] = replace_string_xy(tmp[n_row], n_col, '*')
            if count_char_from_lines(tmp, '#') == K:
                answers += 1
    return [answers]


# 指定位置の文字を置き換える
def replace_string_xy(line, pos, char):
    ret = ''
    for i, x in enumerate(line):
        if i == pos:
            ret += char
        else:
            ret += line[i]
    return ret


# 文字を数える
def count_char_from_line(line, char):
    n_char = 0
    for i in line:
        if i == char:
            n_char += 1
    return n_char


# 文字を数える
def count_char_from_lines(lines, char):
    n_char = 0
    for line in lines:
        n_char += count_char_from_line(line, char)
    return n_char


# パターン取得
def get_pattern(n):
    _, patter = get_pattern_internal(n-1, ['0', '1'])
    return patter


# パターン取得(再起処理内部)
def get_pattern_internal(n, lst):
    if n == 0:
        return 0, lst
    else:
        ret = list()
        for item in lst:
            ret.append('0' + item)
            ret.append('1' + item)
        m, ret = get_pattern_internal(n-1, ret)
        return m, ret


# 引数を取得
def get_input_lines_1stline1stblock_as_n_lines():
    lines = list()
    lines.append(input())
    H, W, K = map(int, lines[0].split(' '))
    for _ in range(H):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['2 3 2', '..#', '###']
        lines_export = [5]
    elif pattern == 2:
        lines_input = ['2 3 4', '..#', '###']
        lines_export = [1]
    elif pattern == 3:
        lines_input = ['2 2 3', '##', '##']
        lines_export = [0]
    elif pattern == 4:
        lines_input = ['6 6 8', '..##..', '.#..#.', '#....#', '######', '#....#', '#....#']
        lines_export = [208]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines_1stline1stblock_as_n_lines()
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = abc173_c(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9324