Letters

Given a matrix N x M. Each cell of the matrix contains some lowercase English letter.How many submatrices are there, that matches both following conditions:

• the submatrix contains at most K cells with letter L.
• all letters, located in all four corner cells of the submatrix, are equal.

Formally, a submatrix's definition is as follows. It is defined by four integers x1, y1, x2, y2 such that 1 ≤ x1 < x2 ≤ n, 1 ≤ y1 < y2 ≤ m. Then the submatrix contains all such cells (x, y) (x is the row number, y is the column number), for which the following inequality holds x1 ≤ x ≤ x2, y1 ≤ y ≤ y2. The corner cells of the matrix are cells (x1, y1), (x1, y2), (x2, y1), (x2, y2).