Після першого дня UJGOI, Сакурако вирішила проаналізувати таблицю результатів. Вона визначає, наскільки хороша таблиця результатів з місця до місця за допомогою функції f(l,r).
Якщо кількість учасників, які мають непарні бали, є непарною на інтервалі (l,r), то g_{odd}(l, r) дорівнює сумі непарних елементів, а в іншому випадку - 0. Якщо кількість учасників, які мають парні бали, є парною на інтервалі (l,r), то g_{even}(l, r) є сумою парних елементів, а в іншому випадку - 0. f(l, r)=g_{odd}(l, r)+g_{even}(l,r).
Отже, якщо жодна з умов не виконується, то f(l,r)=0, а якщо обидві виконуються, то вона дорівнює сумі всіх елементів на інтервалі. Сакурако просить вас знайти суму f(l, r) по всіх інтервалах.
Перший рядок містить одне ціле число (1\le n\le 2\cdot 10^5) — кількість місць у таблиці результатів.
Другий рядок містить цілих чисел a_1, a_2,\dots, a_n (1\le a_i\le 10^9) — бали кожного місця у таблиці результатів.
Виведіть одне ціле число — суму значень f(l,r) по всіх за модулем 10^9+7.
Приклад 1
У першому тесті є такі інтервали (l, r):
— кількість непарних чисел непарна, кількість парних чисел парна, тому сума дорівнює 1;
— кількість непарних чисел парна, кількість парних чисел непарна, тому сума дорівнює 0;
— кількість непарних чисел непарна, кількість парних чисел парна, тому сума дорівнює 3;
— кількість непарних чисел парна, кількість парних чисел непарна, тому сума дорівнює 0;
— кількість непарних чисел непарна, кількість парних чисел парна, тому сума дорівнює 5;
— кількість непарних чисел непарна, кількість парних чисел непарна, тому сума дорівнює 1;
— кількість непарних чисел непарна, кількість парних чисел непарна, тому сума дорівнює 3;
— кількість непарних чисел непарна, кількість парних чисел непарна, тому сума дорівнює 3;
— кількість непарних чисел непарна, кількість парних чисел непарна, тому сума дорівнює 5;
[1, 2, 3] — кількість непарних чисел парна, кількість парних чисел непарна, тому сума дорівнює 0;
[2, 3, 4] — кількість непарних чисел непарна, кількість парних чисел парна, тому сума дорівнює 9;
[3, 4, 5] — кількість непарних чисел парна, кількість парних чисел непарна, тому сума дорівнює 0;
[1, 2, 3, 4] — кількість непарних чисел парна, кількість парних чисел парна, тому сума дорівнює 6;
[2, 3, 4, 5] — кількість непарних чисел парна, кількість парних чисел парна, тому сума дорівнює 6;
[1, 2, 3, 4, 5] — кількість непарних чисел непарна, кількість парних чисел парна, тому сума дорівнює 15.
Отже, сума f(l, r) по всіх дійсних інтервалах (l, r) дорівнює 1+0+3+0+5+1+3+3+5+0+9+6+6+15=57.
( балів): a_i непарне для всіх , n\le 1000;
( балів): n\le 1000;
( балів): a_i непарне для всіх ;
( балів): без додаткових обмежень.