Problem Description

Christmas is approaching, and you have decided to make a holey cake for your friends as a Christmas cake.

The cake batter used to make the holey cake is in the shape of a rectangle with $ R $ rows and $ C $ columns. The region in the $i\ (1\ ≦\ i\ ≦\ R)$ row and $j\ (1\ ≦\ j\ ≦\ C)$ column is referred to as region ($ i $, $ j $). When you eat region ($ i $, $ j $), you gain $ C_{i,j} $ kilocalories. Also, region ($ 1 $, $ 1 $) is the top-left corner, and region ($ R $, $ C $) is the bottom-right corner.

You process this cake batter into a holey cake by following these steps:

• First, determine four integers $ a $, $ b $, $ c $, $d\ (1\ ≦\ a\ ＜\ b\ ≦\ R,\ 1\ ≦\ c\ ＜\ d\ ≦\ C,\ b\ -\ a\ ≧\ 2,\ d\ -\ c\ ≧\ 2)$. Cut out the rectangular part of the cake batter with region ($ a $, $ c $) as the top-left corner and region ($ b $, $ d $) as the bottom-right corner.
• For the part cut out in the previous step, choose one region that is not on the edge (let it be region ($ e $, $ f $) where $a+1\ ≦\ e\ ≦\ b-1,\ c+1\ ≦\ f\ ≦\ d-1$) and remove it, leaving the rest as the holey cake.

The calorie intake of the holey cake is the sum of the calories assigned to the regions that make up the holey cake.

Your health-conscious friends want the holey cake to provide exactly $ K $ kilocalories. You have decided to calculate the total number of possible holey cakes that meet the condition, i.e., the number of ways to choose the six integers $ a $, $ b $, $ c $, $ d $, $ e $, $ f $ that satisfy the above conditions.

Input Format

The input is given from the standard input in the following format:

$ R $ $ C $ $ K $ $ s_1 $ $ s_2 $ : $ s_R $

• The first line contains the number of rows $R\ (3\ ≦\ R\ ≦\ 350)$, the number of columns $C\ (3\ ≦\ C\ ≦\ 350)$, and the desired calorie intake $K\ (0\ ≦\ K\ ≦\ 999,999)$ separated by spaces.
• The next $ R $ lines contain information about the calories of the cake batter. The $i\ (1\ ≦\ i\ ≦\ R)$ line contains a string $ s_i $ of length $ C $. Each character in $ s_i $ is a digit from 1 to 9. The $j\ (1\ ≦\ j\ ≦\ C)$th character from the left in $ s_i $ is equal to the calorie amount $ C_{i,j} $ that increases by including region ($ i $, $ j $) in the holey cake.

Output Format

Output the total number of possible holey cakes on one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4 5 14
54311
11211
17312
11119

Sample Output #1

2

Sample Input #2

6 7 8
1111116
1111111
1111115
1113111
1211111
1111141

Sample Output #2

7

Sample Input #3

3 3 9
211
121
112

Sample Output #3

0

Sample Input #4

8 8 15
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111

Sample Output #4

100

Notes/Hints

Sample Explanation 1

The cake batter is as follows:

5 4 3 1 1
1 1 2 1 1
1 7 3 1 2
1 1 1 1 9

For example, if $ a $ = $ 2 $, $ b $ = $ 4 $, $ c $ = $ 1 $, $ d $ = $ 4 $, the following regions are cut out:

1 1 2 1 1
7 3 1 1 1
1 1 1 1 1

Further, if $ e $ = $ 3 $, $ f $ = $ 2 $, the holey cake will have the following shape (\* represents the hole):

1 1 2 1 1
\* 3 1 1 1
1 1 1 1 1

In this case, the calorie intake is $ 1+1+2+1+1+3+1+1+1+1+1 $ = $ 14 $, which meets the condition. Another way to meet the condition is $ a $ = $ 1 $, $ b $ = $ 3 $, $ c $ = $ 3 $, $ d $ = $ 5 $, $ e $ = $ 2 $, $ f $ = $ 4 $.

Sample Explanation 2

Even if the calorie arrangement of the regions that make up the holey cake is the same, counting different cakes depends on the different places where the cake is cut out and the hole is made.

Sample Explanation 3

There may be cases where no holey cake meets the condition.

见题面 Input 部分

见题面 Output 部分