8. Obrana pobrežia

Kiribatské pobrežie začali nedávno sužovať nájazdy útočných sépií. Sépie priplávajú ku brehu a potom sťahujú do mora slnečníky, lehátka a výletníkov. Minule dokonca odtiahli aj stánok so zmrzlinou.

Určite netreba vysvetľovať, čo by sa stalo s turistickým ruchom, ak by sa to rozkríklo. Kiribatská pobrežná stráž preto rýchlo dostala z príslušného ministerstva dotáciu a dôraznú inštrukciu, nech problém rýchlo vyrieši.

Za peniaze z ministerstva pobrežná stráž nakúpila \(n\) balíst. Balista je mechanické zariadenie, schopné strieľať harpúny po sépiách. Harpúna má samozrejme na sebe uviazané lano, takže trafenú sépiu vie pobrežná stráž vytiahnuť na breh (a tam naporcovať a zjesť).

Úloha

Pobrežie Kiribati si predstavíme ako os \(x\), more bude polrovina zodpovedajúca kladnému \(y\). Na pobreží stojí \(n\) balíst. Z mora sa práve blíži \(n\) sépií. Každú balistu aj každú sépiu považujeme za bod.

Pobrežná stráž by chcela uloviť všetkých \(n\) sépií naraz. Je zjavné, že na to treba každou balistou uloviť inú sépiu. Existuje teda \(n!\) možností, ako priradiť balisty ku sépiám.

Nie všetky možnosti sú však vhodné. Problém je, že keby sme strieľali len tak hala-bala, mohli by sa nám niektoré laná z harpún o seba zamotať. Pobrežná stráž preto musí strieľať takým spôsobom, aby sa tejto nepríjemnosti zaručene vyhla.

Presnejšie: Keď trafíme sépiu harpúnou, lano uviazané o harpúnu tvorí úsečku spájajúcu balistu na brehu s trafenou sépiou vo vode. Priradenie balíst sépiám je dobré vtedy, ak sú všetky tieto úsečky navzájom disjunktné (čiže ak žiadne dve nemajú spoločný bod).

Dané sú súradnice balíst aj sépií. Spočítajte, koľko existuje dobrých priradení balíst sépiám. Vypíšte túto hodnotu modulo \(10^9 + 7\).

Dôležité: V tejto úlohe nie je nutné optimalizovať časovú zložitosť. Presnejšie, ľubovoľné riešenie s polynomiálnou časovou zložitosťou môže dostať plný počet bodov za popis – ale samozrejme, na plný počet bodov musíte riešenie dobre popísať a ukázať o ňom, že naozaj má polynomiálnu časovú zložitosť.

Formát vstupu

V prvom riadku vstupu je celé číslo \(n\). Platí \(1\leq n\leq 50\).

V druhom riadku vstupu je \(n\) celých čísel \(b_1,\dots,b_n\): x-ové súradnice balíst. Balista \(i\) sa teda nachádza na súradniciach \((b_i,0)\).

V treťom riadku je \(n\) celých čísel \(x_1,\dots,x_n\): x-ové súradnice sépií.

Vo štvrtom riadku je \(n\) celých čísel \(y_1,\dots,y_n\): y-ové súradnice sépií.

Všetky súradnice sú od \(-1000\) do \(1000\), vrátane. Všetky \(y_i\) sú navyše kladné. Žiadne dve balisty ani žiadne dve sépie sa nenachádzajú v tom istom bode.

Formát výstupu

Vypíšte jeden riadok a v ňom hodnotu \((p\bmod 10^9 + 7)\), kde \(p\) je počet dobrých priradení balíst sépiám.

Príklady

Input:

2
4 -4
1 2
1 2

Output:

2

Balisty sú na súradniciach \((4,0)\) a \((-4,0)\). Sépie sú na súradniciach \((1,1)\) a \((2,2)\). Sú dve možné priradenia balíst sépiám. Obe sú dobré.

Input:

2
4 -4
4 -4
10 10

Output:

1

Tentokrát je len jedno priradenie balíst sépiám dobré, pri druhom sa laná prekrížia.

Input:

3
-1 0 1
0 0 0
1 2 3

Output:

2

Všimnite si, že sú zakázané aj situácie, v ktorých koniec jednej úsečky leží na inej úsečke. (Inými slovami, lano ide priamo ponad inú sépiu.)

Input:

4
-2 2 98 102
0 1 100 101
1 2 1 2

Output:

4

Input:

9
5 7 8 9 10 11 12 15 18
13 4 1 6 12 7 9 17 5
15 7 11 2 15 1 6 4 5

Output:

10