Givn 2-d grid of n cross m ,consisting of orranges some of which are rotten and some of which are not rotten.Every second,among good oranges that have rotten orange in the adjacent cell on the side EXACTLY ONE ORRANGE BECOMES ROTTEN.What configuration of rotten oranges can be obtained in t seconds.Count the number of such configurations.

Input format:
first line consists of 3 integers n,m and t
Each of next n lines contain m characters.Symbol '$' means orranges are good and '_' orranges are rotten .It is guaranted that there are atleast t good orranges in initial configuration.

output format:
print number of different possible table configuration

Constraints:
1<=n,m<=100
1<=t<=6

TL:
2 sec

Example:

2 2 1
_ $
Output :2

possible configuration:
_ _

_ _