Se dă o permutare {$A = a{~1~},...,a{~N~}$} a mulţimii {${1,...,N}$}. Să se determine valoarea sumei:

<tex>\sum_{\[1 \le i < j \le N} v(a{~i~},...,a{~j~})\]\hspace{1mm} mod 10^9+7</tex>

<tex>\[\sum_{1 \le i < j \le N} v(a_i,...,a_j)\]\hspace{1mm} mod 10^9+7</tex>

h2. Date de intrare

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

Primul rând al fişierului de intrare $seqval.in$ conţine numărul natural $N$.
Al doilea rând conţine elementele permutării $A$ in ordine.

h2. Date de ieşire

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

Fişierul de ieşire $seqval.out$ va conţine răspunsul, pe un singur rând.

h2. Restricţii

h2. Subtaskuri

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

h3. Subtask 1 (20 puncte)
 
* {$N ≤ 200$}
 
h3. Subtask 2 (20 puncte)
 
* {$N ≤ 2 000$}
 
h3. Subtask 3 (40 puncte)
 
* {$N ≤ 200 000$}
 
h3. Subtask 4 (20 puncte)
 
* {$N ≤ 500 000$}

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

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

| 5
  1 2 3 4 5
| 20
|
| 3
  2 3 1
| 1000000006

|
h3. Explicaţie

...

Observăm că în primul exemplu suma cerută este:
{$v(1,2) + ... + v(4,5) + v(1,2,3) + ... + v(3,4,5) + v(1,2,3,4) + v(2,3,4,5) + v(1,2,3,4,5)$}
{$= 4×1 + 3×2 + 2×3 + 1×4$}
{$= 20$}
 
Observăm că în al doilea exemplu suma cerută este {$v(2,3) + v(3,1) + v(2,3,1) = (2 - 1) + (1 - 2) + (2 - 3) = -1$}, iar {$-1 mod 10^9^ + 7 = 10^9^ + 6$}.

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