Family Relay
In 2012, the government of Byteland declared it the Year of Health and decided to construct a running track in the national capital park for the annual family relay race. The park is a rectangle measuring N by M meters, divided into squares of equal size, each with an area of one square meter. This means the park is a grid with N rows and M columns. Rows are numbered from top to bottom starting at one, and columns are numbered from left to right starting at one. Thus, each square can be identified by a pair of numbers (X, Y), where X is the row number and Y is the column number.
Initially, the track was planned to be rectangular, but ecologists from the Ministry of Natural Resources of Byteland recommended a cross-shaped design to meet international standards.
The cross-shaped running track is designed as follows:
A horizontal strip is selected, one square wide and H squares long.
A vertical strip is selected, one square wide and V squares long, intersecting the horizontal strip. Here, H and V are any natural numbers. The square where both strips intersect is called the base square.
Barriers are installed along the entire length of each strip, measuring H - 1 and V - 1 meters long, respectively.
The relay race starts and finishes at the base square, and the race follows the barrier of the running track, as illustrated in the diagram.
Figure 1. Description of the second example, showing 2 possible track options costing 6 bytes each.
The park's squares can either contain a tree or be empty. If a square contains a tree, it occupies the entire square.
The cost of constructing the running track depends on both the number and type of squares. Equipping an empty square for the track costs one byte (the national currency of Byteland), while equipping a square with a tree costs two bytes, as the tree must be removed first.
The government has allocated S bytes for building the running track. Your task is to determine how many different ways there are to construct a cross-shaped running track. Two track constructions are considered different if they involve different sets of squares or different base squares.
Input
The first line of input contains three integers separated by spaces: N, M (2 ≤ N, M ≤ 300) and S (1 ≤ S ≤ 10^9).
The next N lines contain strings of M characters each, describing the park. The j-th character in the i-th string represents the type of square. The character '.' (ASCII 46) indicates an empty square at coordinates (i, j), while the character '#' (ASCII 35) indicates a square with a tree.
Output
The output should be a single integer: the number of different ways to construct the cross-shaped running track.