E. Хоосон тэгш өнцөгтүүд

хугацааны хязгаарлалт 12 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Чамд $n × m$ ($n$ мөртэй $m$ баганатай) ширээ байгаа, ширээний нүд бүр "0" эсвэл "1"-г агуулна.

Чиний даалгавар бол нүднүүдийн хөвөөгөөр ирмэгээ хийсэн, ширээний ирмэгүүдтэй параллел талуудтай дотор нь нэгийн тоо яг к удаа багтсан тэгш өнцөгтүүдийн тоог тооцоолох юм.

Оролт

Эхний мөрөнд хоосон зайгаар тусгаарлагдсан $n$, $m$, $k$  ($1 ≤ n, m ≤ 2500, 0 ≤ k ≤ 6$) ширээний хэмжэээсүүд болон нэгийн тооны шаардагдах тоо болох $3$ ширхэг бүхэл тоонууд байна.

Дараагийн $n$ мөр тус бүр "0" эсвэл "1" байх $m$ ширхэг тэмдэгтүүд агуулна. $j$-дугаар мөрний $i$-дугаар тэмдэгт нь ширээний $j$-дугаар мөр, $i$-дугаар баганын нүдэнд дэх тэмдэгтэд харгалзана.

Гаралт

Нэг тоо хэвлэнэ: яг к ширхэг 1 тоо агуулж буй тэгш өнцөгтүүдийн тоо.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Энхдүүрэн

Жишээ тэстүүд

Оролт
3 3 2
101
000
101
Гаралт
8
Оролт
5 5 1
00000
00000
00100
00000
00000
Гаралт
81
Оролт
5 5 6
01010
10101
01010
10101
01010
Гаралт
12
Оролт
3 3 0
001
010
000
Гаралт
15
Оролт
4 4 0
0000
0101
0000
0000
Гаралт
52
Сэтгэгдлүүдийг ачааллаж байна...