sandwich

Sandwich

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

În Tărâmul Ooo, Jake vrea să pregătească sandwichul magic perfect. Pe o potecă sunt aliniate $n$ ingrediente numerotate de la $1$ la $n$, iar ingredientul $i$ are o valoare de „gust” $a{~i~}$. Magia sandwichului are o regulă ciudată: nu are voie să aleagă două ingrediente alăturate, altfel magia se risipeşte.

!>problema/sandwich?sandwichulperfect.jpg!

Pentru orice segment continuu de ingrediente $a{~l~} a{~l+1~} ... a{~r~}$, Jake poate alege un subşir de poziţii strict crescător (eventual gol) astfel încât nici două poziţii alese să nu fie adiacente. Suma gustului acelui subşir este:
$a{~i{~1~}~} a{~i{~2~}~} ... a{~i{~k~}~}$, cu $l ≤ i{~1~} < i{~1~} < ... < i{~k~} ≤ $r$ şi i{~j~} + 1 < i{~j+1~}$

În Tărâmul Ooo, Jake vrea să pregătească sandwichul magic perfect. Pe o masă sunt aliniate $N$ ingrediente numerotate de la $1$ la $N$, iar ingredientul $i$ are o valoare de „gust” $a{~i~}$.

Definim f(a[l..r]) = suma maximă posibilă pentru un astfel de subşir (se permite subşirul gol).

Pentru orice subsecvenţă de ingrediente $a{~l~} a{~l+1~} ... a{~r~}$, Jake poate alege un subşir de poziţii strict crescător (eventual gol) astfel încât să nu existe două poziţii adiacente alese. Gustul total acelui subşir este: $a{~i{~1~}~} + a{~i{~2~}~} + ... + a{~i{~k~}~}$, cu $l ≤ i{~1~} < i{~2~} < ... < i{~k~} ≤ r$ şi $i{~j~} + 1 < i{~j+1~}$ pentru orice $1 ≤ j < k$.

Jake vrea să ştie câtă magie totală poate aduna, dacă ia în calcul toate segmentele posibile ale potecii. Cu alte cuvinte, calculaţi:

Definim <tex> f(a[l..r]) </tex> = gustul total maxim posibil pentru un astfel de subşir.

S = <tex> $\sum f(a[l..r])$ <tex>

Jake vrea să ştie suma celor mai gustoase sandwichuri pe care le poate face, dacă ia în calcul toate subsecvenţele posibile ale mesei. Cu alte cuvinte, calculaţi:
 
<tex> S = \sum_{1 \leq l \leq r \leq n} f(a[l..r]) </tex>

h2. Date de intrare

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

Fişierul de intrare $sandwich.in$ conţine numerele $N, x, y, z$ şi $a{~1~}$. Şirul $a$ este codificat astfel:
 
$a{~i~} = (a{~i-1~} * x + y) % z$ pentru orice $2 ≤ i ≤ N$

h2. Date de ieşire

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

În fişierul de ieşire $sandwich.out$ afişaţi valoarea lui $S$ modulo 10^9^ + 7.

h2. Restricţii

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

* $1 ≤ N ≤ 5 000 000$
* $1 ≤ x, y ≤ 1 000 000 000$
* $0 ≤ a{~1~} < z ≤ 1 000 000 000$
 
|_. #  |_. Punctaj |_. Restricţii |
| 1 | 4 | $N ≤ 15$ |
| 2 | 11 | $N ≤ 500$ |
| 3 | 13 | $N ≤ 2000$ |
| 5 | 9 | $N ≤ 200 000$ şi $z = 2$|
| 5 | 41 | $N ≤ 200 000$ |
| 6 | 22 | $N ≤ 5 000 000$ |

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 3 1 6 5
| 50

|
h3. Explicaţie

...

$a = [5, 4, 1, 4]$
 
$f(a[1..1]) = 5$
$f(a[1..2]) = 5$
$f(a[1..3]) = 6$
$f(a[1..4]) = 9$
$f(a[2..2]) = 4$
$f(a[2..3]) = 4$
$f(a[2..4]) = 8$
$f(a[3..3]) = 1$
$f(a[3..4]) = 4$
$f(a[4..4]) = 4$
 
$S = 50$

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