시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 128 MB | 0 | 0 | 0 | 0.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 N, M ( 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 <= hi <= 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, c0, w1, c1 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.
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
5 2
W zestawie testowym nr 1 możliwe trasy to:
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번