AT_abc420_f [ABC420F] kirinuki

You are given an $ N \times M $ grid. Each cell contains either `.` or `#`. The information about the symbols written in the cells is given as $ N $ strings $ S_1,S_2,\dots,S_N $ , where the same symbol as the $ j $ -th character of $ S_i $ is written in the cell at the $ i $ -th row from the top and $ j $ -th column from the left. How many rectangular regions consisting of at most $ K $ cells have all cells containing `.`? Formally, count the number of integer tuples $ (l_x,r_x,l_y,r_y) $ that satisfy the following conditions: - $ 1 \le l_x \le r_x \le N $ - $ 1 \le l_y \le r_y \le M $ - $ (r_x-l_x+1) \times (r_y-l_y+1) \le K $ - For all integer pairs $ (i,j) $ satisfying $ l_x \le i \le r_x $ and $ l_y \le j \le r_y $ , the cell at the $ i $ -th row from the top and $ j $ -th column from the left contains `.`.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ K $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

Output the answer.

### Sample Explanation 1 The rectangular regions to count are the following $ 19 $ : - A rectangular region represented by $ (l_x,r_x,l_y,r_y) = (1,2,2,3) $ - A rectangular region represented by $ (l_x,r_x,l_y,r_y) = (2,3,1,2) $ - A rectangular region represented by $ (l_x,r_x,l_y,r_y) = (2,2,1,3) $ - A rectangular region represented by $ (l_x,r_x,l_y,r_y) = (1,3,2,2) $ - $ 4 $ rectangular regions of $ 1 $ row and $ 2 $ columns consisting only of `.` - $ 4 $ rectangular regions of $ 2 $ rows and $ 1 $ column consisting only of `.` - $ 7 $ rectangular regions of $ 1 $ row and $ 1 $ column consisting only of `.` ### Constraints - $ N $ , $ M $ , and $ K $ are integers. - $ 1 \le N,M \le 5 \times 10^5 $ - $ 1 \le N \times M \le 5 \times 10^6 $ - $ 1 \le K \le N \times M $ - $ S_i $ is a string of length $ M $ consisting of `.` and `#`.