给定一个 H 行 W 列的网格；令 (i, j) 为网格中从上到下第 i 行、从左到右第 j 列的格子。 

当 S_{i,j} 为 `.` 时，格子为空格；当 S_{i,j} 为 `#` 时，格子为障碍物。

请计算从某个空格出发，经过 K 次移动（上下左右），不经过障碍物且不重复经过同一个格子的路径数。

具体地，统计满足以下条件的，长度为 K+1 的序列 ((i_0,j_0),(i_1,j_1),\dots,(i_K,j_K))

- 对于每个 0\ \leq\ k\ \leq\ K ，都有 1\ \leq\ i_k\ \leq\ H,\ 1\ \leq\ j_k\ \leq\ W ，且 S_{i_k,j_k} 为 `.`。

- 对于每个 0\ \leq\ k\ \leq\ K-1 ，有 |i_{k+1}-i_k|\ +\ |j_{k+1}-j_k|\ =\ 1 。

- 对于每个 0\ \leq\ k\ <\ l\ \leq\ K ，有 (i_k,j_k)\neq\ (i_l,j_l) 。

> H W K

S_{1,1}S_{1,2}\dots S_{1,W}

S_{2,1}S_{2,2}\dots S_{2,W}

\vdots

S_{H,1}S_{H,2}\dots S_{H,W}

输出满足条件的路径数量。

总共有两种可能的路径

-   (1,1) \rightarrow (2,1) \rightarrow (2,2)

-   (2,2) \rightarrow (2,1) \rightarrow (1,1)

n,m \leq 10