CF253D Table with Letters - 2

Vasya has recently started to learn English. Now he needs to remember how to write English letters. He isn't sure about some of them, so he decided to train a little. He found a sheet of squared paper and began writing arbitrary English letters there. In the end Vasya wrote $ n $ lines containing $ m $ characters each. Thus, he got a rectangular $ n×m $ table, each cell of the table contained some English letter. Let's number the table rows from top to bottom with integers from 1 to $ n $ , and columns — from left to right with integers from 1 to $ m $ . After that Vasya looked at the resulting rectangular table and wondered, how many subtables are there, that matches both following conditions: - the subtable contains at most $ k $ cells with "a" letter; - all letters, located in all four corner cells of the subtable, are equal. Formally, a subtable's definition is as follows. It is defined by four integers $ x_{1},y_{1},x_{2},y_{2} $ such that $ 1

The first line contains three integers $ n,m,k $ $ (2

Print a single integer — the number of required subtables.

There are two suitable subtables in the first sample: the first one's upper left corner is cell $ (2,2) $ and lower right corner is cell $ (3,3) $ , the second one's upper left corner is cell $ (2,1) $ and lower right corner is cell $ (3,4) $ .