$N$ 個の座席が横一列に並んでおり、左から $1, 2, \dots, N$ と番号が付けられています。最初、どの座席にも人は座っていません。 これから $1, 2, \dots, K$ の番号の付けられた $K$ 人の人が順に、以下のルールで座席を $1$ つ選びその座席に座ります。

1. 人が座っていない座席であって、以下の「条件」を満たすものがあるような場合、その中から $1$ つを選んで座る。
   • 条件：左右に隣り合う座席であって、人が座っているようなものが存在しない。
2. そのような座席がない場合は、人が座っていない席から $1$ つを選んで座る。

., # からなる長さ $N$ の文字列 $S$ が与えられます。$S$ に含まれる # の個数はちょうど $K$ 個です。 $K$ 人の座り方であって上記のルールに従うもののうち、$S$ の $i$ 文字目が # ならばいずれかの人が座席 $i$ に座っており、$S$ の $i$ 文字目が . ならばどの人も座席 $i$ に座らないような座り方の個数を求めてください。 ただし、2つの座り方が異なるとは、ある $j$ ($1 \leq j \leq K$) が存在して人 $j$ が座った座席が $2$ つの座り方で異なることを指します。

答えは非常に大きくなる場合があるので、$998244353$ で割ったあまりを出力してください。また、条件を満たす座り方がない場合は $0$ を出力してください。

• $N$ は整数で、 $1 \leq N \leq 3000$
• $K$ は整数で、 $1 \leq K \leq N$
• $S$ は # 、 . からなる長さ $N$ の文字列
• $S$ に含まれる # は $K$ 個

• $1 \leq K \leq 8$ を満たすデータセットに正解した場合は $25$ 点が与えられる。
• $K = N$ を満たすデータセットに正解した場合は $25$ 点が与えられる。

入力は以下の形式で標準入力から与えられる。

$N$ $K$
$S$

答えを $1$ 行で出力せよ。