問題文の条件から、1 行に置けるコマの個数は高々 \(\left\lfloor\frac{W}{2}\right\rfloor\) 個になるのを利用します。

\(H,W\) がともに偶数の場合、 \(L\) の上界として\(\frac{W}{2} \times H = \frac{HW}{2}\) があり、これは市松模様状にコマを置くと達成できます。1 行目のコマの置き方は #.#.#. … と .#.#.# … の 2 通りで、このとき他の行の置き方も一意に定まるので \(2\) 通りが答えになります。

\(H,W\) に奇数が含まれる場合、適宜 \(H,W\) を入れ替えることで次の \(2\) つのいずれかの場合に帰着します。

• \(H\) が偶数で \(W\) が奇数である場合
• \(H,W\) がともに奇数で \(H \geq W\) である場合

このとき \(L\) は \(H \times \frac{W-1}{2}\) が上界です。
この上界を達成できることを確認します。上界を達成する配置がある時、各行は #.#..#.#.#. のように 1 ヵ所だけ . が隣り合っています。また、適当な \(2\) 行を抜き出すと、以下の図のように .. が \(1\) つ左か \(1\) つ右にずれることが確認できます。この事実を利用すれば、上界を達成する並べ方が存在することは直ちに確認できます。

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

さて、上界を達成する配置の数え上げを行います。以下では行方向の添え字は \(\text{mod }H\)、列方向の添え字は \(\text{mod }W\) で考えます。valid な配置と \(A_i :=\) 「\((i,j) =\) . かつ \((i,j + 1) =\) . を満たす \(j\)」 である長さ \(H\) の整数列 \(A\) を一対一対応させると、次の条件を満たす \(A\) の個数を数えられればよいです。

• \(1 \leq A_i \leq W\)
• \(1 \leq i \leq H\) について \(A_{i +1} - A_{i} \equiv 1, -1 \pmod W\)

これは \(H,W\) の大小に応じて場合分けを行えば高速に計算できます。

• \(H \leq 10^5\) の場合は答えを \(\mathrm{O}(H)\) 個の二項係数の和で表して計算します。
• \(W \leq 10^5\) の場合は \((x+x^{-1})^H \bmod{(x^W-1)}\) の定数項を畳み込み + ダブリングで計算します。

よってこの問題を \(\mathrm{O}( \min(H,W) \log H \log W)\) で解くことができました。

実装例 (C++)

• 追記

「畳み込み + ダブリング」の部分で詰まっている or 定数倍を悪くしている人が多いようなので簡単に追記します。
\(A_i\) から \(1\) を引いて \(0 \leq A_i \lt W\) で考えます。 \(A_1 = 0\) の場合を \(W\) 倍したものが答えなので \(A_1 = 0\) として解きます。\(dp_{i,j} :=\) (\(A_i\) が \(j\) である場合の数) とすると

\[dp_{i,j} = dp_{i-1,j-1} + dp_{i-1,j+1}\]

です。(ここで 2 番目の添え字は \(\text{mod }W\) 上で考えています。) また、便宜上 \(A_{H+1} = A_1\) とすると、求める答えは \(dp_{H+1,0}\) となります。

この DP を、長さ \(W\) の巡回畳み込みを利用して高速化することを考えます。長さ \(W\) の巡回畳み込みとは、長さ \(W\) の列 \(s,t\) から以下の式を満たす長さ \(W\) の列 \(u\) を得る操作をいいます。

\[u_{k} = \sum_{0 \leq j < W} s_i t_{(j-i) \bmod W}\]

ちなみに長さ \(W\) の巡回畳み込みは、通常の多項式の畳み込みの結果に \(\text{mod }(x^W-1)\) を取る操作と等価です。

DP を多項式と巡回畳み込みを用いて表現すると、 \(f(x) = (x + x^{W-1})\) として \(f(x)^H \bmod (x^W - 1)\) の \(0\) 次の係数が答えとなることが確認できると思います。

また、多項式 \(f, g\) を長さ \(W\) で巡回畳み込みする操作は次のような C++ のコードで atcoder::convolution のみを利用して \(\mathrm{O}(W \log W)\) で計算できます。

using mint = atcoder::modint998244353;
vector<mint> mul(vector<mint>& f, vector<mint>& g) {
  auto h = atcoder::convolution(f, g);
  for (int i = W; i < (int)h.size(); i++) h[i % W] += h[i];
  h.resize(W);
  return h;
};

\(f(x)^H \bmod (x^W - 1)\) は二分累乗法を利用すれば \(\mathrm{O}(\log H)\) 回の巡回畳み込みで計算できるので、全体で \(\mathrm{O}(W \log W \log H)\) で計算できます。