Rezolvare PBinfo #4363

Fie un șir de întregi \( {a}_{1}, …, {a}_{k} \). Vom numi valoarea lui \( {a}_{1}, …, {a}_{k} \), pe care o vom nota \( value({a}_{1}, …, {a}_{k}) \), numărul maxim 2x astfel încât 2x divide \( {a}_{1} + … + {a}_{k} \). Spre exemplu, dacă k = 3 și a1 = 8, a2 = 3, a3 = 1 atunci a1 + a2 + a3 = 12 iar valoarea secvenței este 4.

Cerința

Vei primi o secvență de n numere naturale \( {a}_{1}, …, {a}_{n} \). Calculează restul impărțirii sumei tuturor subsecvențelor continue ale șirului \( {a}_{1}, …, {a}_{n} \) la 1.000.000.007, care este egal cu:

Cu alte cuvinte, \( S({a}_{1}, …, {a}_{n}) \) este restul împărțirii sumei valorilor \( value({a}_{i}, …, {a}_{j}) \) pentru toate 1 ≤ i ≤ j ≤ n prin împărțirea la 1.000.000.007.

Date de intrare

Programul citește de pe prima linie numărul n. A doua linie va conține întregii \( {a}_{1}, …, {a}_{n} \), separați prin câte un spațiu.

Date de ieșire

Programul va afișa o singură linie care conține numărul \( S({a}_{1}, …, {a}_{n}) \).

Restricții și precizări

• 1 ≤ n ≤ 200.000
• 1 ≤ ai ≤ 1.000.000
• \( {a}_{1} + … + {a}_{n} ≤ 1.000.000 \)
• Pentru 13 puncte, ai = 1, n ≤ 200
• Pentru 16 puncte, \( {a}_{1} + … + {a}_{n} ≤ 200 \)
• Pentru 5 puncte, n ≤ 200
• Pentru 20 puncte, n ≤ 5000
• Pentru 21 puncte, \( {a}_{1} + … + {a}_{n} ≤ 200.000 \)
• Pentru 25 puncte, fără restricții suplimentare

Exemplul 1:

Intrare

3
1 2 3

Ieșire

8

Explicație

Valorile tuturor subsecvențelor continue sunt:

• value(1) = 1
• value(1, 2) = 1
• value(1, 2, 3) = 2
• value(2) = 2
• value(2, 3) = 1
• value(3) = 1

Astfel, S(1, 2, 3) este restul împărțirii sumei valorilor la 1.000.000.007, adică 8 pentru acest exemplu.

Exemplul 2:

Intrare

5
2 4 1 2 4

Ieșire

25

Explicație

Valorile tuturor subsecvențelor continue sunt:

• value(2) = 2
• value(2, 4) = 2
• value(2, 4, 1) = 1
• value(2, 4, 1, 2) = 1
• value(2, 4, 1, 2, 4) = 1
• value(4) = 4
• value(4, 1) = 1
• value(4, 1, 2) = 1
• value(4, 1, 2, 4) = 1
• value(1) = 1
• value(1, 2) = 1
• value(1, 2, 4) = 1
• value(2) = 2
• value(2, 4) = 2
• value(4) = 4

Astfel, S(2, 4, 1, 2, 4) este restul împărțirii sumei valorilor la 1.000.000.007, adică 25 pentru acest exemplu.