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.
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.
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.
Example 1
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.
( 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.