Score : 300 points
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:
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.
.
or #
.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}
Print an integer representing the number of choices of rows and columns satisfying the condition.
2 3 2 ..# ###
5
Five choices below satisfy the condition.
2 3 4 ..# ###
1
One choice, which is choosing nothing, satisfies the condition.
2 2 3 ## ##
0
6 6 8 ..##.. .#..#. #....# ###### #....# #....#
208