UJGOI Skor Taxtası#410

UJGOI Skor Taxtası

1 saniyə
256 meqabayt
Hard

UJGOI-nin ilk günündən sonra, Sakurako bal cədvəlini təhlil etməyə qərar verdi. O, bal cədvəlinin -ci yerdən -ci yerə kimi olan hissəsinin nə qədər yaxşı olduğunu f(l,r) funksiyası ilə təyin edir.

Əgər (l,r) intervalında tək balların sayı təkdirsə, g_{odd}(l, r) oradakı tək elementlərin cəmi olur, əks halda 0-dır. Əgər (l,r) intervalında cüt balların sayı cütdürsə, g_{even}(l, r) oradakı cüt elementlərin cəmi olur, əks halda 0-dır. f(l, r)=g_{odd}(l, r)+g_{even}(l,r).

Beləliklə, şərtlərdən heç biri yerinə yetirilmirsə, onda f(l,r)=0, əgər hər ikisi yerinə yetirilirsə, onda bu, intervaldakı bütün elementlərin cəminə bərabərdir. Sakurako sizdən bütün intervallar üçün f(l, r)-lərin cəmini tapmağı xahiş edir.

Input

Birinci sətirdə bir tam ədəd (1\le n\le 2\cdot 10^5) — bal cədvəlində olan yerlərin sayı.

İkinci sətirdə tam ədəd a_1, a_2,\dots, a_n (1\le a_i\le 10^9) — bal cədvəlindəki hər yerin balları verilir.

Output

Bir tam ədəd çıxarın — bütün intervalları üçün f(l,r) dəyərlərinin cəmi. Cavabın 10^9+7-yə qalığını çıxarın.

Examples

Example 1

Loading
Loading

Note

Birinci testdə aşağıdakı intervallar var:

  •  — tək ədədlərin sayı təkdir, cüt ədədlərin sayı cütdür, buna görə cəm 1-dir;

  •  — tək ədədlərin sayı cütdür, cüt ədədlərin sayı təkdir, buna görə cəm 0-dır;

  •  — tək ədədlərin sayı təkdir, cüt ədədlərin sayı cütdür, buna görə cəm 3-dür;

  •  — tək ədədlərin sayı cütdür, cüt ədədlərin sayı təkdir, buna görə cəm 0-dır;

  •  — tək ədədlərin sayı təkdir, cüt ədədlərin sayı cütdür, buna görə cəm 5-dir;

  •  — tək ədədlərin sayı təkdir, cüt ədədlərin sayı təkdir, buna görə cəm 1-dir;

  •  — tək ədədlərin sayı təkdir, cüt ədədlərin sayı təkdir, buna görə cəm 3-dür;

  •  — tək ədədlərin sayı təkdir, cüt ədədlərin sayı təkdir, buna görə cəm 3-dür;

  •  — tək ədədlərin sayı təkdir, cüt ədədlərin sayı təkdir, buna görə cəm 5-dir;

  • [1, 2, 3] — tək ədədlərin sayı cütdür, cüt ədədlərin sayı təkdir, buna görə cəm 0-dır;

  • [2, 3, 4] — tək ədədlərin sayı təkdir, cüt ədədlərin sayı cütdür, buna görə cəm 9-dur;

  • [3, 4, 5] — tək ədədlərin sayı cütdür, cüt ədədlərin sayı təkdir, buna görə cəm 0-dır;

  • [1, 2, 3, 4] — tək ədədlərin sayı cütdür, cüt ədədlərin sayı cütdür, buna görə cəm 6-dır;

  • [2, 3, 4, 5] — tək ədədlərin sayı cütdür, cüt ədədlərin sayı cütdür, buna görə cəm 6-dır;

  • [1, 2, 3, 4, 5] — tək ədədlərin sayı təkdir, cüt ədədlərin sayı cütdür, buna görə cəm 15-dir.

Beləliklə, bütün düzgün (l, r) intervalları üzrə f(l, r)-lərin cəmi 1+0+3+0+5+1+3+3+5+0+9+6+6+15=57-dir.

Scoring

  • ( bal): a_i bütün -lər üçün təkdir, n\le 1000;

  • ( bal): n\le 1000;

  • ( bal): a_i bütün -lər üçün təkdir;

  • ( bal): əlavə məhdudiyyətlər olmadan.