mere

Emanuel, proaspăt ajuns la Oxford, este nerăbdător să se apuce de treabă și să înceapă... să culeagă mere. Poziția în care aceasta se află în livadă se poate identifica folosind perechea de coordonate $(x, y)$, inițial aflându-se în punctul $(0, 0)$. Datorită amplasării copacilor din livadă, Emanuel se poate mișca pe orizontală cu o viteză maximă $V_A$, iar pe verticală cu o altă viteză maximă $V_B$.

Începând ziua de muncă, Emanuel își notează în carnețelul lui coordonatele și momentul de timp $T_i$ în care recoltează merele pentru fiecare din cei $N$ meri din care va culege mere, urmând să-i justifice șefului recolta sa. Pentru că în tot acest timp el încerca să demonstreze ipoteza lui Riemann, își notează în caiet mereu doar una din cele două coordonate $X_i$ la care se afla, uneori cea orizontală, alteori cea verticală.

La finalul zilei, el își dă seama de greșeala făcută și se întreabă cât de plauzibil este traseul lui, pentru a-i explica șefului întâmplarea și a nu fi trimis în Cambridge la cules de pere. Pentru a determina probabilitatea traseului, el va presupune pentru fiecare coordonată notată, pe rând, că aceasta este pe orizontală, iar apoi pe verticală și va număra toate configurațiile posibile.

Cerință

Se va implementa funcția

int count(int N, int VA, int VB, int *X, int *T)

ce va returna numărul de configurații posibile modulo $1\ 000\ 000\ 007$. $N$ reprezintă numărul de evenimente (recolte), $V_A$ și $V_B$ vitezele maxime pe cele două direcții. $X$ și $T$ sunt două șiruri de $N$ elemente, indexate de la $0$, ce memorează una din coordonate $X$ respectiv momentul de timp $T$ pentru fiecare eveniment.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $1 \leq V_{A}, V_{B} \leq 10^9$
• $-10^9 \leq X_i \leq 10^9$
• $1 \leq T_i \leq 10^9$
• Valorile $T_i$ sunt date în ordine crescătoare
• Enunțul și punctajele nu corespund cu cele din timpul concursului

Subtask 1 (6 puncte)

• $N \leq 20$

Subtask 2 (24 puncte)

• $N \leq 1000$

Subtask 3 (41 puncte)

• $N \leq 100\ 000$

Subtask 4 (29 puncte)

• $N \leq 200\ 000$

Exemplu

Se dau $N = 4, V_A = 3, V_B = 2$ și evenimentele:
$X_0 = 2, T_0 = 1$
$X_1 = 7, T_1 = 3$
$X_2 = 1, T_2 = 4$
$X_3 = 8, T_3 = 5$

Există $2$ moduri posibile de atribuire a coordonatelor:

• $X_1$ și $X_3$ pe orizontală (cu viteza $v_A$), $X_0$ și $X_2$ pe verticală (cu viteza $v_B$). Avem următoarele perechi (poziție, timp)
  Pe orizontală: $(0, 0), (7, 3), (8, 5)$
  Pe verticală: $(0, 0), (2, 1), (1, 4)$
• $X_0$, $X_1$, $X_3$ pe orizontală, $X_2$ pe verticală.
  Pe orizontală: $(0, 0), (2, 1), (7, 3), (8, 5)$
  Pe verticală: $(0, 0), (1, 4)$

Nu am putea avea $X_0$ și $X_2$ pe orizontală, $X_1$ și $X_3$ pe verticală, deoarece ar însemna să ne mișcăm pe verticală de la perechea $(0, 0)$ la $(7, 3)$; imposibil deoarece am parcurge $7$ unități în $3$ secunde, iar viteza maximă pe verticală este $2$.