Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$.

When the frog's current cell is $(x,y)$, in one jump it can move to any cell $(x+a,y+b)$ within the grid that satisfies all of the following conditions.

• $a, b$ are non-negative integers
• $1\le a+b\le K$

However, some cells are holes, and the frog cannot move to those cells. If $c_{i,j}$ is #, cell $(i,j)$ is a hole, and if it is ., it is not. It is guaranteed that cell $(1,1)$ and cell $(H,W)$ are not holes.

Find the number of paths along which the frog can move from $(1,1)$ to $(H,W)$. Since the answer can be very large, find it modulo $998244353$.

Constraints

• $H,W,K$ are positive integers.
• $2\le \textcolor{red}{HW}\le 10^6$
• $1\le K \le H+W-2$
• $c_{i,j}$ is . or #.
• $c_{1,1}$ and $c_{H,W}$ are ..

Input

$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}$

Output

Print on 1 line the number of paths along which the frog can move from $(1,1)$ to $(H,W)$, modulo $998244353$.

Sample

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

6

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

53

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

6080