Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_16_04 - Trzy posągi króla

Bajtolomeusz uwielbia spacerować ścieżkami biegnącymi przez jego królewski ogród. Zieleniec ten ma kształt prostokąta i przecina go N ścieżek biegnących z południa na północ oraz M ścieżek biegnących z zachodu na wschód. Ścieżki w każdej z tych dwóch grup mają przyporządkowane kolejno numery, odpowiednio od 1 do N oraz od 1 do M. Król zaczyna zawsze spacer w południowo-zachodnim narożniku ogrodu (czyli tam, gdzie zaczynają się ścieżki o numerach 1) a kończy go w narożniku północno-wschodnim (czyli tam, gdzie spotykają się ścieżki o najwyższych numerach). Podczas spaceru król porusza się tylko na wschód lub na północ.

Ostatnio Bajtolomeusz rozkazał, aby trzy ze skrzyżowań, jakie tworzą ścieżki, upiększyć posągami przedstawiającymi Jego Wysokość. Władca zastanawia się teraz, na ile sposobów może odbyć spacer przez ogród, tak, aby przejść przez co najmniej jedno z tych wyróżnionych skrzyżowań. Ponieważ liczba ta może być bardzo duża, Bajtolomeusza interesuje jedynie reszta z dzielenia jej przez 1000000007.

Wejście

W pierwszej linii liczba testów t (1 ≤ t ≤ 1000000).
Dla każdego testu dane zapisane są w dwóch kolejnych liniach.
W pierwszej - dwie liczby całkowite N i M (2N,M105) oznaczające odpowiednio liczbę ścieżek biegnących z południa na północ i liczbę ścieżek biegnących z zachodu na wschód.
W drugiej linii - trzy pary liczb całkowitych xi i yi (dla i=1..3) oznaczających współrzędne skrzyżowań z posągami (1xiN, 1yiM). 

Wyjście

Dla każdego testu, w osobnej linii liczba możliwych spacerów króla Bajtolomeusza modulo 1000000007

Przykład

Wejście:
2
4 3
3 1 1 3 2 3
2 2
1 1 1 2 2 2 Wyjście:
6
2

Dodane przez:Witold Długosz
Data dodania:2014-05-22
Limit czasu wykonania programu:1s-4.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2014-05-24 16:52:33 Witold D³ugosz
Nie.

Ostatnio edytowany: 2014-05-24 16:55:31
2014-05-24 16:49:37 Mateusz Wasylkiewicz
Czy dwa różne posągi mogą się znajdować na tym samym skrzyżowaniu?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.