AT_arc196_b [ARC196B] Torus Loop

$ H $ 行 $ W $ 列のグリッドがあります。 行には上から順に $ 0,1,\ldots, H-1 $ の番号が、列には左から順に $ 0,1,\ldots,W-1 $ の番号がついています。 行 $ i $ 、列 $ j $ のマスをマス $ (i,j) $ と表すことにします。 $ H $ 個の文字列 $ S_0, S_1, \ldots, S_{H-1} $ が与えられます。それぞれの文字列は `A` と `B` のみからなる長さ $ W $ の文字列です。 各マスには、以下の $ 2 $ 種類のタイルのいずれかを配置します。 $ S_i $ の $ j+1 $ 文字目 $ (0\leq j \leq W-1) $ を $ S_{ij} $ としたとき、マス $ (i,j) $ に配置するタイルの種類は $ S_{ij} $ です。 - 種類 A：タイルの表面に、隣接する $ 2 $ 辺の中点どうしを結ぶ線分が一本描かれている  - 種類 B：タイルの表面に、向かい合う $ 2 $ 辺の中点どうしを結ぶ線分が一本描かれている  タイルは自由に回転可能です。タイルの表面に描かれた線分のみに注目したとき、種類 A のタイルを回転する方法は $ 4 $ 通り、種類 B のタイルを回転する方法は $ 2 $ 通りあります。よって、線分が作る模様のみによってタイルの配置方法を区別したとき、タイルを配置する方法の数は、種類 A のタイルの数 $ a $ 、種類 B のタイルの数 $ b $ を用いて、 $ 4^a\times 2^b $ 通りと表されます。 このうち、グリッドをトーラスとして見たときにタイルに描かれた線分が行き止まりを持たないようにタイルを配置する方法の数を $ 998244353 $ で割ったあまりを出力してください。 ここで、グリッドをトーラスとして見たときにタイルに描かれた線分が行き止まりを持たないとは、具体的には、すべてのマス $ (i,j) $ について以下の $ 2 $ 条件をともに満たすことを言います。 - 次の $ 2 $ つが、両方とも存在する、あるいはどちらも存在しない。 - マス $ (i,j) $ のタイルの右辺の中点を端点とする、マス $ (i,j) $ のタイルの表面に描かれた線分 - マス $ (i,(j+1)\bmod W) $ のタイルの左辺の中点を端点とする、マス $ (i,(j+1)\bmod W) $ のタイルの表面に描かれた線分 - 次の $ 2 $ つが、両方とも存在する、あるいはどちらも存在しない。 - マス $ (i,j) $ のタイルの下辺の中点を端点とする、マス $ (i,j) $ のタイルの表面に描かれた線分 - マス $ ((i+1)\bmod H,j) $ のタイルの上辺の中点を端点とする、マス $ ((i+1)\bmod H,j) $ のタイルの表面に描かれた線分 例えば、次の配置方法は条件を満たします。  次の配置方法は条件を満たしません。具体的には、マス $ (0,2) $ のタイルの右辺の中点を端点とする線分が存在しないのに対し、マス $ (0,0) $ のタイルの左辺の中点を端点とする線分は存在するので、条件を満たしません。  $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各ケースは以下の形式で与えられる。 > $ H $ $ W $ $ S_0 $ $ S_1 $ $ \vdots $ $ S_{H-1} $

各テストケースに対する、問題文中の条件を満たすタイルの配置方法の数を $ 998244353 $ で割ったあまりを改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースにおける正しい配置の一つの例として、以下の画像のようにタイルを配置する方法があります。  ### Constraints - $ 1 \le T \le 10^5 $ - $ 2 \le H,W $ - $ HW\leq 10^6 $ - $ S_i\,(0\le i\le H-1) $ は `A` と `B` のみからなる長さ $ W $ の文字列 - すべてのテストケースにわたる $ HW $ の総和は $ 10^6 $ 以下 - $ T, H, W $ は整数