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

h3. Subtask 1 (20 puncte)

* {$N &le 200$}

* {$N ≤ 200$}

h3. Subtask 2 (20 puncte)

* {$N &le 2 000$}

* {$N ≤ 2 000$}

h3. Subtask 3 (40 puncte)

* {$N &le 200 000$}

* {$N ≤ 200 000$}

h3. Subtask 4 (20 puncte)

* {$N &le 500 000$}

* {$N ≤ 500 000$}

h2. Exemplu

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

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

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