In the bioinformatics laboratory, scientists are conducting experiments on the spread of artificially created viruses. For the experiment, a special laboratory setup is used, which is a table of n × m cells. A living cell is placed in each cell. Scientists infect some cells with the virus, in total no more than 8 cells are initially infected.
Every second, among uninfected cells that have an infected cell in the adjacent cell, exactly one cell becomes infected with the virus.
Scientists became interested in what configurations of infected cells can be obtained in t seconds. First, they want to count the number of such configurations. Help them do it.
Input data format
The first line of the input file contains integers n, m and t (1 ≤ n, m ≤ 100, 1 ≤ t ≤ 6) — table sizes and number of seconds. Each of the next n lines contains m characters. The character "." means that in the initial configuration the cell is not infected, and the symbol "*" — that is infected. Quantity «*» in the table does not exceed 8. It is guaranteed that there are at least t uninfected cells in the initial configuration.
Output data format
Print the number of different possible table configurations after t seconds.
|
Enter |
Output |
2 2 1
*.
.. |
2 |
2 2 2
*.
.. |
3 |
2 2 3
*.
.. |
1 |