Hints: https://atcoder.jp/contests/arc197/editorial/12878

---

[1] Overall positional relation

Most will notice that the four tiles must occupy the “top-left,” “top-right,” “bottom-left,” and “bottom-right” positions. Let us prove this first.

As usual, number the rows \(1\) to \(H\) and the columns \(1\) to \(W\). Let \((i, j)\) denote the cell at row \(i\) and column \(j\). Paint black the cells \((i,j)\) such that both \(i\) and \(j\) are multiples of \(N\).

Then, a tile always covers exactly one black cell. From the constraints, there are at most four black cells. Thus, in a valid placement, \(2N\leq H,W\) holds, and all of the following are necessary:

• There is exactly one tile containing \((N,N)\).
• There is exactly one tile containing \((N,2N)\).
• There is exactly one tile containing \((2N,N)\).
• There is exactly one tile containing \((2N,2N)\).

Call these tiles top-left, top-right, bottom-left, and bottom-right tiles.

---

[2] Counting

Let the top-left, top-right, bottom-left, and bottom-right tiles have their upper-left corners at \((a_1,b_1)\), \((a_2,b_2)\), \((a_3,b_3)\), and \((a_4,b_4)\), respectively. Let us make it clear when these tiles do not overlap.

First, it is easy to count placements where no two adjacent tiles overlap. These yield the following inequalities:

• \(1\leq a_1,\quad a_1+(N-1)< a_3,\quad a_3+(N-1)\leq H\)
• \(1\leq a_2,\quad a_2+(N-1)< a_4,\quad a_4+(N-1)\leq H\)
• \(1\leq b_1,\quad b_1+(N-1)< b_2,\quad b_2+(N-1)\leq W\)
• \(1\leq b_3,\quad b_3+(N-1)< b_3,\quad b_4+(N-1)\leq W\)

It is also possible to count the number of ways to set \(a_i,b_i\) to satisfy these. For example, if we let \(a_3'=a_3-N\), the first condition can be written as \(1\leq a_1 \leq a_3' \leq H-2N+1\), so the count of \((a_1,a_3)\) is represented by a binomial coefficient; the overall count is the product of four such binomial coefficients.

From this count, subtract the cases where a non-adjacent pair overlaps, that is, the following placements:

• No two adjacent tiles overlap.
• The top-left and bottom-right tiles overlap, or the top-right and bottom-left tiles overlap.

Under the non-adjacency condition, it is impossible that both pairs overlap simultaneously. Furthermore, the counts for these pairs are clearly equal. Thus, it suffices to count the cases where the top-left and bottom-right overlap. Here, we have two independent sets of conditions for rows and columns; for rows we have the following conditions:

• \(1\leq a_2,\quad a_2 +(N-1)<a_4,\quad a_4\leq a_1+(N-1),\quad a_1+(N-1)<a_3,\quad a_3+(N-1)\leq H\).

Substitute \(a'_3=a_3-N\) and \(a'_4=a_4-N\) to rewrite as \(1\leq a_2\leq a_4'<a_1\leq a_3' \leq H-2N+1\), for which the count is again obtained as a binomial coefficient. The same goes for columns.

Eventually, for \(2N\leq H,W\leq 3N-1\), the answer can be expressed as a polynomial in \(x=H-2N\) and \(y=W-2N\), and computed in \(O(1)\) time per test case.

• Sample implementation: https://atcoder.jp/contests/arc197/submissions/65381628