cho.sh

특별한 학생증

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

NLCS Jeju 학생들은 교내에서 학생증(lanyard)을 착용해야 한다. 준석이는 학교의 통제 정책을 싫어하기 때문에 학생증을 착용하지 않고 다니는데, 선생님에게 걸리는 바람에 쫓기고 있다.

추격전을 벌이고 있는 준석이와 선생님을 목격한 교장 선생님은 학교를 미로로 바꾸었다. 미로는 가로 NN, 세로 MM의 2차원 격자로 표현될 수 있다. 좌상단에서 가로로 xx칸, 세로로 yy칸 떨어져 있는 칸은 (x,y)(x, y)로 표현한다. 미로상의 각 칸은 비어 있거나, 포털이 설치되어 있거나, 벽으로 막혀 있다. (0,0)(0, 0)와 (N−1,M−1)(N-1, M-1)은 비어 있음이 보장된다.

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

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

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

준석이가 이동할 때 거치는 칸의 목록을 ‘경로’라고 정의하자. 가능한 경로의 가짓수를 세는 프로그램을 작성하시오.

입력

입력의 첫 줄에 NN과 MM, KK가 공백으로 구분되어 주어진다. NN과 MM은 각각 미로의 가로·세로 칸 수를 나타낸다. KK는 포털 쌍의 수를 나타낸다.

다음 MM 줄에 미로에 대한 정보가 주어진다. MM개의 줄 중 ii번째의 줄은 길이 NN인 문자열로, ii번째 줄의 jj번째 문자는 (j−1,i−1)(j-1, i-1)의 정보를 나타낸다.

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

다음 KK 줄에 각 포털 쌍에 관한 정보가 주어진다. 각 줄에 네 정수 x_1x\_1, y_1y\_1, x_2x\_2, y_2y\_2가 공백으로 구분되어 주어지며, (x_1,y_1)(x\_1, y\_1)과 (x_2,y_2)(x\_2, y\_2) 사이를 잇는 포털 쌍이 존재함을 의미한다. 각 포털의 좌표는 서로 다르며, 포털은 미로상에 P로 표시된 지점상에만 위치함이 보장된다.

출력

첫 번째 줄에 (0,0)(0, 0)에서 (N−1,M−1)(N-1, M-1)까지를 잇는 경로의 가짓수를 출력한다. 결과가 매우 클 수 있기 때문에, 결과를 109+710^9+7로 나눈 나머지를 출력한다.

제한

  • 1≤N,M≤2 0001 \leq N, M \leq 2\ 000
  • 0≤K≤min⁡(⌊NM−22⌋,500 000)0 \leq K \leq \min\left(\left\lfloor\frac{NM-2}{2}\right\rfloor, 500\ 000\right)

힌트

나머지 연산에 대하여 다음이 성립한다.

  • (A+B) mod C=(A mod C)+(B mod C) mod C(A + B) \bmod C = \\{(A \bmod C) + (B \bmod C)\\} \bmod C