問題文

ある文字列 $X$ が叩きやすいとは以下の条件を満たすことを言います。

• $X_i=$ . を満たすすべての奇数 $i$ について、$X_{i-1},X_{i+1}$ はそれぞれ存在するならば . である。

なお、この問題における文字列のindexは $1$ から始まります。

またある文字列 $Y,Y^{\prime }$ について、$Y^{\prime }$ が $Y$ のアレンジであるとは以下の条件をすべて満たすことを言います。

1. $|Y^{\prime }|=|Y|$
2. $Y^{\prime }$ は .,d,k のみからなる
3. $Y_i\ne$ . ならば $Y_i^{\prime }=Y_i$
4. $Y_i=$ . かつ $Y_{i+1}\ne$ . ならば $Y_i^{\prime }\ne Y_{i+1}(i<|Y|)$

ここで .,d,k のみからなる長さ $16N$ の文字列 $S$ が与えられます。

$S$ のアレンジ $S^{\prime }$ のうち、叩きやすいものはいくつありますか？ $998244353$ で割ったあまりを求めてください。

入力

$N$
$S_{1\dots 16}$
$S_{17\dots 32}$
$⋮$
$S_{16N-15\dots 16N}$

• $N$ は $1$ 以上 $12500$ 以下の整数
• $S$ は .,d,k のみからなる長さ $16N$ の文字列
• $S$ は $16$ 文字ごとに改行区切りで与えられる

出力

$S$ のアレンジ $S^{\prime }$ のうち、叩きやすいものの個数を $998244353$ で割ったあまりを出力し、最後に改行してください。

サンプル

4
ddddkkddd.d.kkdd
ddddkkddkkddkkdd
ddddkkddd.d.kkdd
ddddkkddkkddkkdd

16

4
k..kk.k.kk..k..k
k.k.kk..k..kk.k.
kk..k..kk.k.kk..
k..kk.k.kk..k..k

764411904

6
.ddkdd.kddk.kdd.
kk..............
d.....kk......d.
ddk.......k.k...
.ddkdd.kddk.kdd.
dd....d.d.kkk...

398264397

8
d.....k.d...k.k.
d.dkd.kkd...d.k.
d...k...d.kkd.k.
d.d.k...k...d.k.
k...d.k.k...k.d.
k.kkd.k.d...k.d.
k...k.d.k.k.d.k.
d.kkd.k.d...d...

228829591