Treasure Hunt

Chef lives in an $N \times M$ grid. He is currently participating in a treasure hunt, and has two items left to find. Chef knows that the Manhattan distance between the cells containing these two items is exactly $k$. He wants to know, in how many different pairs of cells can the two items be present? Let $A_k$ be the number of desired pairs when the value of Manhattan distance between the two c