특별한 학생증

NLCS Jeju 학생들은 교내에서 학생증(lanyard)을 착용해야 한다. 준석이는 학교의 통제 정책이 싫어서 학생증을 차지 않고 다닌다. 그러다 선생님에게 걸려서 지금 쫓기고 있다.

준석이와 선생님의 추격전을 목격한 교장 선생님은 학교를 미로로 바꾸었다. 미로는 가로 $N$칸, 세로 $M$칸의 2차원 격자다. 좌상단에서 가로로 $x$칸, 세로로 $y$칸 떨어진 칸은 $(x, y)$로 나타낸다. 미로의 각 칸은 빈칸, 포털이 설치된 칸, 벽으로 막힌 칸 중 하나다. $(0, 0)$과 $(N-1, M-1)$은 빈칸임이 보장된다.

각 포털은 다른 포털 하나와 연결되어 있다. 연결된 두 포털이 포털 쌍을 이룬다.

준석이는 다음 규칙에 따라 $(0, 0)$에서 $(N-1, M-1)$로 이동하려고 한다.

• 뛰어서 이동하는 경우, $(x, y)$에서 $(x+1, y)$ 또는 $(x, y+1)$로 이동할 수 있다. 단, 이동하려는 칸이 벽으로 막혀 있으면 이동할 수 없다.
• 포털이 설치된 칸에 있으면 포털을 이용해 이동할 수 있다. 포털을 이용하면 연결된 포털로 순간 이동한다. 미로가 급하게 만들어져서 포털은 매우 불안정하다. 따라서 포털을 하나 사용하면 모든 포털이 고장 나서 더는 사용할 수 없게 된다.

준석이가 이동할 때 거치는 칸을 차례대로 나열한 목록을 '경로'라고 정의한다. 가능한 경로의 가짓수를 세는 프로그램을 작성하시오.

첫 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $N$과 $M$은 각각 미로의 가로 칸 수와 세로 칸 수를 나타내고, $K$는 포털 쌍의 수를 나타낸다.

다음 $M$개의 줄에 미로 정보가 주어진다. $i$번째 줄은 길이 $N$인 문자열이며, 그 $j$번째 문자는 $(j-1, i-1)$의 정보를 나타낸다.

• 0은 빈칸을 나타낸다. $(0, 0)$과 $(N-1, M-1)$은 빈칸임이 보장된다.
• 1은 벽을 나타낸다.
• P는 포털을 나타낸다.

다음 $K$개의 줄에 각 포털 쌍의 정보가 주어진다. 각 줄에는 정수 $x_1$, $y_1$, $x_2$, $y_2$가 공백으로 구분되어 주어지며, $(x_1, y_1)$과 $(x_2, y_2)$의 포털이 서로 연결되어 있음을 뜻한다. 포털의 좌표는 모두 다르고, 포털은 미로에서 P로 표시된 칸에만 있음이 보장된다.

첫 번째 줄에 $(0, 0)$에서 $(N-1, M-1)$까지 이어지는 경로의 가짓수를 출력한다. 값이 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

• $1 \leq N, M \leq 2\ 000$
• $0 \leq K \leq \min\left(\left\lfloor\frac{NM-2}{2}\right\rfloor, 500\ 000\right)$

나머지 연산에서는 다음이 성립한다.

$(A + B) \bmod C = \{(A \bmod C) + (B \bmod C)\} \bmod C$