Code lock

Time limit2sMemory limit1024 MB

Summary

Count the connected sets of exactly k button cells on a grid of up to 30 by 30 cells, where cells sharing a side connect.

Level: Medium7 of 10
Topics: Bit manipulation, BFS, Brute force
Solved: No attempts yet

Problem

A company named <<Замки и замки>> recently developed a new type of code lock for installing on gates. The lock panel is a rectangle $w$ cells wide and $h$ cells high. Some cells have buttons.

A code is entered by pressing $k$ buttons at the same time. To make the code easier to remember, the buttons used in it must form a connected region. A region is connected if you can get from any cell of the region to any other cell by moving only between cells of the region that share a side. An important measure of the lock's reliability is the number of different codes that can be entered on it.

Write a program that computes this number.

Input

The first line contains three integers $h$ , $w$ , and $k$ ( $1 \le h, w \le 30$ ; $1 \le k \le 10$ ). Each of the next $h$ lines contains $w$ characters. The character # marks a button, and . marks an empty cell.

Output

Print one integer: the number of codes that satisfy the requirements.

Hint

The figure shows one possible code for the second input.

Examples2

Example 1
Input
```
2 2 2
#.
##
```
Expected output
```
2
```

Example 2

Input

5 6 7
.#....
##.##.
..#.#.
.####.
.....#

Expected output