Diapazon

diapazon

== include(page="template/taskheader" task_id="diapazon") ==

În continuare, vom folosi cuvântul "diapazon" ca sinonim pentru termenul de "interval". De ce? Fiindcă este distractiv.
 
Se dau $N$ diapazoane $[Left[i], Right[i]]$ numerotate de la $1$ la $N$. Diapazonul $i$ se afla la inaltimea $N - i$. Primul diapazon, cel mai de sus, incepe sa cada. Toate celelalte sunt fixe. Daca pe parcursul caderii, diapazonul $1$ atinge un alt diapazon $j$ cel putin intr-un punct, atunci se va reuni cu acel diapazon cu probabilitate de $P[j] / Q[j]$. Din reuniunea a două diapazoane $[A, B]$ şi $[C, D]$ se obţine diapazonul $[min(A, C), max(B, D)]$. Se cere să se afle care este lungimea medie aşteptată a diapazonului cu numărul $1$ la finalul căderii (i.e după ce a ajuns la o înălţime strict mai mică decât toate celelalte diapazoane).

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $diapazon.in$ contine cele pe prima linie numarul $N$. Pe fiecare dintre urmatoarele $N$ linii este descris cate un diapazon prin patru numere intregi: $Left, Right, P, Q$, reprezentand un diapazon $[Left, Right]$ care are probabilitate $P / Q$ sa se uneasca cu diapazonul care cade.

Fişierul de intrare $diapazon.in$ ...

h2. Date de ieşire

În fişierul de ieşire $diapazon.out$ trebuie sa contina pe prima linie un numar natural $X < 1.000.000.007$. Daca raspunsul este un numar rational $U / V$, atunci $X$ are proprietatea $X * V ≡ U (mod 1.000.000.007)$.

În fişierul de ieşire $diapazon.out$ ...

h2. Restricţii

* $0 < P < Q ≤ 1.000$
* $0 < Left ≤ Right ≤ 1.000.000$
* Pentru teste in valoare de *20* puncte $N ≤ 200$
* Pentru teste in valoare de *60* puncte $N ≤ 2.000$
* Pentru teste in valoare de *100* puncte $N ≤ 100.000$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. diapazon.in |_. diapazon.out |

| 5
  35 64 58 873
  41 70 407 729
  18 90 165 628
  10 57 33 104
  60 69 152 466
| 779316733
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

Raspunsul este aproximativ $49.813963$.

...

== include(page="template/taskfooter" task_id="diapazon") ==

== include(page="template/taskfooter" task_id="diapazon") ==