## KRECT - Counting K-Rectangle

 English Vietnamese

Given a M*N square board. Each square contains a letter of the English alphabet ('A' .. 'Z').

A K-rectangle of the board is a rectangle whose sides are parallel to the sides of the board, and contains exactly K different types of letter.

For example, with this 4*3 board:

```CED
CEB
CBC
DDA
```

The rectangle [(1,1), (2,2)] is a 2-rectangle of the board because it contains 2 different letters: C and E.

Given M, N, K and the M*N board. Determine how many K-rectangles there are in the board.

### Input

The first line contains 3 integers M, N and K. (1 ≤ M, N ≤ 100, 1 ≤ K ≤ 26)

The following M lines, each contains N letters of the English alphabet ('A' .. 'Z')

### Output

Write one integer - the number of K-rectangles in the given board.

### Example

```Input:
4 3 3
CED
CEB
CBC
DDA

Output:
12

```

 < Previous 1 2 Next > Jelle van den Hooff: 2009-10-02 05:48:01 O((NM)^2) works great, but you have to keep the constant factor _low_. stjepan: 2009-10-02 05:48:01 My solution is a O(n^2*m^2) algorithm and it is the fastest at the moment. Last edit: 2009-06-03 19:22:36 Robert Gerbicz: 2009-10-02 05:48:01 I think no. By a possible swapping of row<->column my solution's complexity is O(min(m,n)^2*max(m,n)*|A|), where A is the alphabet, so here |A|=26. Last edit: 2009-05-06 19:19:19 .:: Pratik ::.: 2009-10-02 05:48:01 Just a hint. Does this problem allow a O(n^4) solution to clear? Thanks.