Sandwich

sandwich

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

!>problema/sandwich?sandwichulperfect.jpg!

În Ţinutul 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.

Î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~}$.

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:
<tex> a_{i_1} <tex> + <tex> a_{i_2} <tex> + ... + <tex> a_{i_k} <tex>, cu l &le; <tex> i_1 <tex> &lt; <tex> i_2 <tex> &lt; ... &lt; <tex> i_k <tex> &le; r şi <tex> i_j <tex> + 1 &lt; <tex> i_{j+1} <tex>

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$.

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

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

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

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>

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

h2. Date de intrare

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$

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

h2. Date de ieşire

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

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

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 |

| 4 3 1 6 5
| 50

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

|
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") ==