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₁, y₁, x₂, y₂ such that 1 ≤ x₁ < x₂ ≤ n, 1 ≤ y₁ < y₂ ≤ m. Then the subtable contains all such cells (x, y) (x is the row number, y is the column number), for which the following inequality holds x₁ ≤ x ≤ x₂, y₁ ≤ y ≤ y₂. The corner cells of the table are cells (x₁, y₁), (x₁, y₂), (x₂, y₁), (x₂, y₂).

Vasya is already too tired after he's been writing letters to a piece of paper. That's why he asks you to count the value he is interested in.