AT_abc420_f [ABC420F] kirinuki

$ N \times M $ のグリッドが与えられます。各マスには `.` または `#` が書かれています。 マスに書かれている記号の情報は $ N $ 個の文字列 $ S_1,S_2,\dots,S_N $ として与えられ、上から $ i $ 行目の左から $ j $ マス目には $ S_i $ の $ j $ 文字目と同じ記号が書かれています。 全てのマスに `.` が書かれており、 $ K $ 個以下のマスで構成される長方領域は全部でいくつありますか? 厳密には、以下の条件を満たす整数の組 $ (l_x,r_x,l_y,r_y) $ の数を数えてください。 - $ 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 $ - 全ての $ l_x \le i \le r_x $ 、 $ l_y \le j \le r_y $ を満たす整数組 $ (i,j) $ について、上から $ i $ 行目の左から $ j $ マス目には `.` が書かれている。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

答えを出力せよ。

### Sample Explanation 1 数えるべき長方領域の数は以下の $ 19 $ 個です。 - $ (l_x,r_x,l_y,r_y) = (1,2,2,3) $ で表現される長方領域 - $ (l_x,r_x,l_y,r_y) = (2,3,1,2) $ で表現される長方領域 - $ (l_x,r_x,l_y,r_y) = (2,2,1,3) $ で表現される長方領域 - $ (l_x,r_x,l_y,r_y) = (1,3,2,2) $ で表現される長方領域 - 縦 $ 1 $ マス、横 $ 2 $ マスの `.` のみからなる長方領域 $ 4 $ 個 - 縦 $ 2 $ マス、横 $ 1 $ マスの `.` のみからなる長方領域 $ 4 $ 個 - 縦 $ 1 $ マス、横 $ 1 $ マスの `.` のみからなる長方領域 $ 7 $ 個 ### Constraints - $ N,M,K $ は整数 - $ 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 $ は `.` と `#` からなる長さ $ M $ の文字列