Cemetery Piety Sum

In a newly established cemetery, the area is modeled as an N×M grid. Each cell is either occupied by an evergreen tree (denoted by T) or is an unassigned grave plot (denoted by .). Devout local residents pre‐book a grave plot hoping that its piety is high. The piety of a grave plot is defined as the number of "crosses" that can be formed with that plot as the center.

A cross centered at a grave plot located at \( (x,y) \) is formed by selecting exactly \( k \) evergreen trees in each of the four directions (up, down, left and right) that satisfy the following conditions:

• Upward: There exist \( k \) trees at positions \( (x_{1,1}, y), (x_{1,2}, y), \dots, (x_{1,k}, y) \) with \( x_{1,1} < x_{1,2} < \cdots < x_{1,k} < x \).
• Downward: There exist \( k \) trees at positions \( (x_{2,1}, y), (x_{2,2}, y), \dots, (x_{2,k}, y) \) with \( x < x_{2,1} < x_{2,2} < \cdots < x_{2,k} \).
• Leftward: There exist \( k \) trees at positions \( (x, y_{3,1}), (x, y_{3,2}), \dots, (x, y_{3,k}) \) with \( y_{3,1} < y_{3,2} < \cdots < y_{3,k} < y \).
• Rightward: There exist \( k \) trees at positions \( (x, y_{4,1}), (x, y_{4,2}), \dots, (x, y_{4,k}) \) with \( y < y_{4,1} < y_{4,2} < \cdots < y_{4,k} \).

Since the ordering in each direction is unique when the trees are taken in increasing order, the number of ways to choose trees in one direction is simply \( \binom{n}{k} \), where \( n \) is the number of trees available in that direction. Thus, the piety of a grave plot at \( (x, y) \) is computed as:

[ \text{piety}(x,y) = \binom{U}{k} \times \binom{D}{k} \times \binom{L}{k} \times \binom{R}{k} ]

where:

• \( U \) is the number of trees above (in the same column with row index less than \( x \));
• \( D \) is the number of trees below (in the same column with row index greater than \( x \));
• \( L \) is the number of trees to the left (in the same row with column index less than \( y \));
• \( R \) is the number of trees to the right (in the same row with column index greater than \( y \)).

The task is to compute the sum of the piety values for all grave plots in the cemetery.

inputFormat

The input begins with a line containing three integers ( N ), ( M ) and ( k ) (the number of rows, columns, and the required number of trees in each direction respectively). The following ( N ) lines each contain a string of length ( M ) consisting only of characters T and ., where T represents an evergreen tree and . represents an unassigned grave plot.

outputFormat

Output a single integer representing the total piety sum of all grave plots. For a grave plot at ( (x, y) ), if the counts of trees upward, downward, leftward, and rightward are ( U ), ( D ), ( L ), and ( R ) respectively, its contribution is [ \binom{U}{k} \times \binom{D}{k} \times \binom{L}{k} \times \binom{R}{k}, ] with ( \binom{n}{k} = 0 ) if ( n < k ).

sample

3 3 1
TTT
T.T
TTT

1