We will use the fact that, from the condition in the statement, we can place at most \(\left\lfloor\frac{W}{2}\right\rfloor\) pieces in a row.

If both \(H\) and \(W\) are even, an upperbound for \(L\) is \(\frac{W}{2} \times H = \frac{HW}{2}\), which can be achieved by placing the pieces in a checkered pattern. There are two ways for the top row: #.#.#. … and .#.#.# …, which uniquely determine the placement in the remaining rows, so the answer is \(2\).

If at least one of \(H\) and \(W\) is odd, we can reduce that case to one of the following by swapping \(H\) and \(W\) if necessary:

• \(H\) is even, and \(W\) is odd;
• both \(H\) and \(W\) are odd, and \(H \geq W\).

Here, an upperbound for \(L\) is \(H \times \frac{W-1}{2}\).
We will verify that it is achievable. If there is a placement that achieves it, each row contains exactly one pair of adjacent .’s, which looks like #.#..#.#.#.. Additionally, the positions of ..’s in any two adjacent rows differ by one square, as shown in the figure below. Using these facts, we can immediately confirm that there is a placement that achieves the upperbound.

#.#..#.#.#.
.#.#..#.#.#

Now, let us count the placements that achieve the upperbound. Below, we consider the indices for rows \(\text{mod }H\), and for columns \(\text{mod }W\). By making one-to-one correspondence between a valid placement and an integer sequence \(A\) of length \(H\) where \(A_i\) is \(j\) such that \((i,j) =\) . and \((i,j + 1) =\) ., we can solve the problem by counting sequences \(A\) that satisfy the following conditions:

• \(1 \leq A_i \leq W\);
• \(A_{i +1} - A_{i} \equiv 1, -1 \pmod W\), for each \(1 \leq i \leq H\).

We can count them efficiently by dividing the case according to the magnitude relationship between \(H\) and \(W\).

• If \(H \leq 10^5\), represent the answer as a sum of \(\mathrm{O}(H)\) binomial coefficients and compute it.
• If \(W \leq 10^5\), compute the constant term of \((x+x^{-1})^H \bmod{(x^W-1)}\) with convolution + binary lifting.

Now the problem is solved in \(\mathrm{O}( \min(H,W) \log H \log W)\) time.

Sample Implementation (C++)