시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 128 MB0000.000%

문제

Góry Górzyste reprezentowane są przez siatkę N*M liczb w N wierszach po M kolumn każdy, oznaczających wysokości terenu w punktach kratowych. Wychodząc naprzeciw potrzebom narciarzy, niedawno wybudowano K wyciągów narciarskich łączących wybrane pary punktów, przy czym wszystkie wyciągi pracują jednokierunkowo, wciągając narciarzy z punktu położonego niżej do punktu położonego wyżej.

Trasa narciarska to ciąg wjazdów wyciągami (podczas których stale zwiększa się wysokość, na której znajduje się narciarz) a następnie ciąg zjazdów do punktu w którym trasa się rozpoczynała, przy czym każdy zjazd to zmiana miejsca o jedną pozycję w jednym z czterech podstawowych kierunków. Każdy zjazd musi odbywać się z pola położonego wyżej do pola położonego niżej.

Kurorty narciarskie w Górach Górzystych chcą reklamować się hasłem: Mamy X (mod 109+7) tras narciarskich. Znając listę wyciągów i tabelę wysokości w poszczególnych punktach oblicz wartość liczby X.

입력

W pierwszej linii wejścia znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) opisująca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

Pierwsza linia opisu zestawu testowego zawiera parę oddzielonych spacjami, opisanych w treści liczb naturalnych NM ( 1 <= N, M <= 100 ). Następne N linii opisuje kolejne wiersze tabelki wysokości (w kolejności od 1 do N). Każda z nich zawiera po M liczb całkowitych oznaczających wysokości hi w kolejnych punktach danego wiersza ( 0 <= h<= 109 ) (wysokości wymienione są w kolejności od pierwszej kolumny do M-tej).

W następnej linii znajduje się liczba naturalna  K  ( 1 <= K <= 300 ) oznaczająca liczbę wyciągów. Ostatnie K linii zawiera po 4 liczby całkowite w0, c0w1c1 oznaczające, że z punktu (w0,c0) istnieje wyciąg do punktu (w1,c1). Każdy wyciąg kończy się na wyższej wysokości niż zaczyna.

출력

Dla każdego zestawu należy w osobnej linii wypisać resztę z dzielenia liczby tras narciarskich przez 109+7.

예제 입력 1

2
2 2
1 2
2 3
3
1 1 1 2
1 1 2 1
1 2 2 2
2 2
1 2
0 1
2
1 1 1 2
1 1 1 2

예제 출력 1

5
2

힌트

W zestawie testowym nr 1 możliwe trasy to:

  • (1,1) -> (1,2) -> (1,1)
  • (1,1) -> (1,2) -> (2,2) -> (1,2) -> (1,1)
  • (1,1) -> (1,2) -> (2,2) -> (2,1) -> (1,1)
  • (1,1) -> (2,1) -> (1,1)
  • (1,2) -> (2,2) -> (1,2)

Na przykładzie zestawu testowego nr 2 widzimy, że może istnieć wiele wyciągów łączących dane dwa punkty.

출처

Contest > Spot > SpringSpot 2011 2-4번