問題文

縦 $H$ 行、横 $W$ 行のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ で表します。

カエルの現在位置のマスを $(x,y)$ としたとき、1回のジャンプで以下の条件をすべて満たすグリッド内のマス $(x+a,y+b)$ のうちいずれかに移動することができます。

• $a, b$ は非負整数
• $1\le a+b\le K$

ただし、いくつかのマスは穴になっていて、そのマスには移動することが出来ません。$c_{i,j}$ が # のときマス $(i,j)$ が穴であることを、 . のときそうでないことを表します。マス $(1,1)$ およびマス $(H,W)$ は穴でないことが保証されています。

カエルが $(1,1)$ から $(H,W)$ まで移動することができる経路の数を求めてください。ただし、答えは非常に大きくなることがあるので、 $998244353$ で割った余りを求めてください。

制約

• $H,W,K$ は正整数である。
• $2\le \textcolor{red}{HW}\le 10^6$
• $1\le K \le H+W-2$
• $c_{i,j}$ は . か # である。
• $c_{1,1}$ および $c_{H,W}$ は . である。

入力

$H$ $W$ $K$
$c_{1,1}c_{1,2}\dots c_{1,W}$
$c_{2,1}c_{2,2}\dots c_{2,W}$
$\vdots$
$c_{H,1}c_{H,2}\dots c_{H,W}$

出力

カエルが $(1,1)$ から $(H,W)$ まで移動することができる経路の数を $998244353$ で割った余りを 1 行で出力してください。

サンプル

3 3 2
...
##.
.#.

6

5 4 3
...#
.###
#...
###.
.#..

53

4 7 9
.......
.......
.......
.......

6080