퀸 움직이기

숙제를 하지 않고 체스와 조합론에 빠져있던 은재가 생활관에 체스판을 하나 들고 왔다. 이 체스판은 특이해서 $8 \times 8$ 형태의 기본적인 판 뿐만 아니라 $17 \times 19$ 크기나 심지어 $1 \times 100$의 크기처럼 자유자재로 판의 크기를 조절할 수 있다.

체스 고수가 되기 위해서 열심히 체스를 두던 은재는 수많은 패배 끝에, 상대 기물의 수비가 약한 약점 칸을 찾아서 공략하는 것이 중요하다는 걸 깨닫게 되었다. 조합론에 빠진 은재는 퀸을 움직여서 상대의 약점 칸으로 보내는 방법이 얼마나 있을지 궁금해서 하라는 체스는 두지 않고 다음과 같은 질문을 던지게 된다.

체스에서 퀸이 가장 중요한 기물인데, 지금 내 퀸이 있는 위치에서 정확하게 $K$번 움직여서 원하는 위치로 보내는 방법이 얼마나 될까?

현재 체스판에는 퀸의 이동을 방해하는 장애물들과 은재의 퀸이 있다. 장애물이 없을 수도 있다.

체스판은 $N$행 $M$열로 구성되어 있고, $r$행 $c$열의 칸은 $(r, c)$로 나타낸다. $(1 \le r \le N$; $1 \le c \le M)$ 또한, 체스판의 각 칸은 장애물이 있는 칸이거나 없는 칸이다.

초기에 퀸의 위치는 $(R\_s, C\_s)$, 퀸을 보내고자 하는 위치는 $(R\_e, C\_e)$이며, 아래 규칙에 따라 퀸을 움직일 수 있다.

• 현재 칸을 $(R, C)$라고 할 때, 다음 $8$가지 방향 중 하나의 방향으로 원하는 거리만큼 움직일 수 있다.

  • 위 — $(R - 1, C), (R - 2, C), (R - 3, C), \cdots$
  • 아래 — $(R + 1, C), (R + 2, C), (R + 3, C), \cdots$
  • 왼쪽 — $(R, C - 1), (R, C - 2), (R, C - 3), \cdots$
  • 오른쪽 — $(R, C + 1), (R, C + 2), (R, C + 3), \cdots$
  • 왼쪽 위 대각선 — $(R - 1, C - 1), (R - 2, C - 2), (R - 3, C - 3), \cdots$
  • 오른쪽 위 대각선 — $(R - 1, C + 1), (R - 2, C + 2), (R - 3, C + 3), \cdots$
  • 왼쪽 아래 대각선 — $(R + 1, C - 1), (R + 2, C - 2), (R + 3, C - 3), \cdots$
  • 오른쪽 아래 대각선 — $(R + 1, C + 1), (R + 2, C + 2), (R + 3, C + 3), \cdots$

• 정한 방향으로 움직일 때 장애물이 있는 칸을 지날 수 없다.

• 체스판 밖으로 나가거나 장애물이 있는 칸으로 움직일 수 없다.

• 두 번 연속으로 같은 방향으로 움직일 수 없다.

• 퀸을 제자리에 두고 턴을 넘기는 것은 불가능하다.

은재를 위해 은재가 퀸을 $K$번 움직여서 $(R\_e, C\_e)$ 칸으로 보낼 수 있는 경우의 수를 구하는 프로그램을 작성해보자!

첫 번째 줄에 세 정수 $N$, $M$, $K$가 주어진다.

$i + 1$번째 줄에 문자열 $S\_i = S\_{i1} S\_{i2} \cdots S\_{iM}$이 주어진다. $(i, j)$ 칸에 장애물이 있으면 $S\_{ij}=$#이고, $(i, j)$ 칸에 장애물이 없으면 $S\_{ij}=$.이다. $(1 \le i \le N$; $1 \le j \le M)$

$N+2$번째 줄에 두 정수 $R\_s$, $C\_s$가 주어진다.

$N+3$번째 줄에 두 정수 $R\_e$, $C\_e$가 주어진다.

문제의 정답을 $998\\,244\\,353$으로 나눈 나머지를 출력한다.

• $1 \le N, M, K \le 100$
• $1 \le R\_s, R\_e \le N$
• $1 \le C\_s, C\_e \le M$
• $(R\_s, C\_s)$와 $(R\_e, C\_e)$에는 장애물이 없음