문제1611--MovieSeating

### 1611: MovieSeating

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 261  통과: 74
[제출] [채점기록] [묻고답하기]

#### 문제 설명

Elly and some of her friends (possibly none) are going to the movies. Their company consists of numFriends people, including Elly. Since they don't want to be spread across the entire hall, they decided to sit either in the same row or in the same column (though not necessarily next to one another).

Your are given a String[] hall representing the layout of seats in the theater that are already taken. The j-th character of the i-th element of hall will be '#' if the seat at row i, column j is already taken and '.' if it is empty.

Print the number of different ways for Elly and her friends to choose numFriends different empty seats so that their seating requirement is fulfilled. Two ways are considered different if there exists a person in their company that will sit in different seats in these two ways.

#### 입력 설명

The first line of the input gives the number of test cases, T (1 <= T <= 200).

Each test case starts with three positive integers numFriends, which is between 1 and 8, inclusive, and rc, which is between 1 and 50, inclusive.

For next r lines, length c string representing r-th line of hall is given.

#### 출력 설명

For each test case, print the number of different ways as explained in the problem statement, in one line.

#### 입력 예시 Copy

4
2 3 4
.#..
.##.
....
2 3 3
..#
.##
...
5 4 8
..####..
.###.##.
.######.
#.#.#.#.
8 1 8
........

#### 출력 예시 Copy

34
16
0
40320