뱀 이동

Putata는 노트북에서 유명한 뱀 게임을 하고 있다. 뱀은 $n \times m$ 크기의 격자 위에서 움직이며, 일부 칸에는 장애물이 있을 수 있다. 뱀은 좌표쌍의 수열 $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$로 표현되고, $k$는 뱀의 길이다. 머리는 $(x_1, y_1)$에, 꼬리는 $(x_k, y_k)$에 있으며, 인접한 몸의 부분은 변을 공유하는 칸에 놓인다.

뱀은 문자열로 주어진 명령을 따라 움직인다. 명령은 다섯 종류다.

• L: 뱀을 왼쪽으로 한 칸 움직인다. 머리는 $(x_1, y_1 - 1)$로 이동한다.
• R: 뱀을 오른쪽으로 한 칸 움직인다. 머리는 $(x_1, y_1 + 1)$로 이동한다.
• U: 뱀을 위로 한 칸 움직인다. 머리는 $(x_1 - 1, y_1)$로 이동한다.
• D: 뱀을 아래로 한 칸 움직인다. 머리는 $(x_1 + 1, y_1)$로 이동한다.
• S: 뱀의 길이를 1 줄인다. 꼬리 칸이 지워지고 길이는 $k - 1$이 된다. $k = 1$일 때는 이 명령을 사용할 수 없다.

머리가 움직이면 나머지 몸의 부분도 함께 움직인다. $i$번째 부분($2 \le i \le k$)은 명령 실행 전 $(i - 1)$번째 부분이 있던 위치로 옮겨 간다. 뱀은 장애물이 있는 칸이나 격자 밖으로 들어갈 수 없다. 또한 뱀은 자기 자신과 충돌할 수 없으므로, 두 몸의 부분이 같은 칸을 차지해서는 안 된다.

머리를 현재 꼬리가 있는 칸으로 옮기는 것은 허용된다. 실제로는 꼬리가 빠져나가는 순간 머리가 그 칸에 들어가는 상황이다. $k = 2$일 때는 명령 한 번으로 머리와 꼬리를 맞바꾸는 것도 허용된다.

$f(i, j)$를 머리가 $(i, j)$에 도달하는 데 필요한 최소 명령 수라고 하자. 도달할 수 없으면 $f(i, j) = 0$이다. 다음 값을 구하라. $\left(\sum_{i=1}^n\sum_{j=1}^m f(i,j)^2\right) \bmod 2^{64}$

첫 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($1 \le n, m \le 3000$, $1 \le k \le \min\{nm, 10^5\}$). 각각 격자의 크기와 뱀의 길이다.

다음 $k$개의 줄에는 $i$번째 부분의 위치 $x_i$, $y_i$가 주어진다 ($1 \le x_i \le n$, $1 \le y_i \le m$, $|x_i - x_{i+1}| + |y_i - y_{i+1}| = 1$). 모든 좌표쌍은 서로 다르며, 각 부분은 장애물이 없는 칸에 있다.

다음 $n$개의 줄에는 길이 $m$인 문자열이 주어진다. .은 빈 칸, #은 장애물이다.

답을 나타내는 정수 하나를 한 줄에 출력한다.