AT_abc461_d [ABC461D] Count Subgrid Sum = K

$ H \times W $ のグリッドがあり、各マスには $ 0 $ または $ 1 $ の整数が書き込まれています。 各マスに書き込まれた整数の情報は $ H $ 個の長さ $ W $ の文字列 $ S_1,S_2,\dots,S_H $ として与えられます。 $ S_i $ の $ j $ 文字目が `0` である時はグリッドの上から $ i $ 行目、左から $ j $ 列目に $ 0 $ が書き込まれており、 $ S_i $ の $ j $ 文字目が `1` である時はグリッドの上から $ i $ 行目、左から $ j $ 列目に $ 1 $ が書き込まれています。 書き込まれた整数の総和が $ K $ となる長方形領域がいくつあるか求めてください。 厳密には、以下の条件を全て満たす整数の四つ組 $ (r_1,c_1,r_2,c_2) $ がいくつあるか求めてください。 - $ 1 \le r_1 \le r_2 \le H $ - $ 1 \le c_1 \le c_2 \le W $ - グリッドの上から $ i $ 行目、左から $ j $ 列目に書き込まれた整数を、 $ r_1 \le i \le r_2, c_1 \le j \le c_2 $ を満たす全ての整数組 $ (i,j) $ について足し合わせた値が $ K $ である。

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

答えを出力せよ。

### Sample Explanation 1 書き込まれた整数の総和が $ K $ となる長方形領域は以下の $ 8 $ 個です。 - 上から $ 1 $ 行目から $ 2 $ 行目、左から $ 1 $ 列目から $ 2 $ 列目を抜き出した長方形領域 - 上から $ 1 $ 行目から $ 2 $ 行目、左から $ 1 $ 列目から $ 3 $ 列目を抜き出した長方形領域 - 上から $ 1 $ 行目から $ 2 $ 行目、左から $ 2 $ 列目から $ 4 $ 列目を抜き出した長方形領域 - 上から $ 1 $ 行目から $ 3 $ 行目、左から $ 2 $ 列目から $ 3 $ 列目を抜き出した長方形領域 - 上から $ 1 $ 行目から $ 3 $ 行目、左から $ 3 $ 列目から $ 4 $ 列目を抜き出した長方形領域 - 上から $ 2 $ 行目から $ 2 $ 行目、左から $ 1 $ 列目から $ 4 $ 列目を抜き出した長方形領域 - 上から $ 2 $ 行目から $ 3 $ 行目、左から $ 1 $ 列目から $ 2 $ 列目を抜き出した長方形領域 - 上から $ 2 $ 行目から $ 3 $ 行目、左から $ 2 $ 列目から $ 3 $ 列目を抜き出した長方形領域 ### Constraints - $ H,W $ は $ 1 $ 以上 $ 500 $ 以下の整数 - $ K $ は $ 0 $ 以上 $ HW $ 以下の整数 - $ S_i $ は `0`, `1` からなる長さ $ W $ の文字列