لوحة تسجيل UJGOI#410

لوحة تسجيل UJGOI

ثانية
256 ميغابايت
Hard

بعد اليوم الأول من 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) على جميع الفترات.

Input

السطر الأول يحتوي على عدد صحيح واحد (1\le n\le 2\cdot 10^5) — عدد الأماكن في لوحة التسجيل.

السطر الثاني يحتوي على عدد صحيح a_1, a_2,\dots, a_n (1\le a_i\le 10^9) — الدرجات لكل مكان في لوحة التسجيل.

Output

أخرج عدد صحيح واحد — مجموع قيم f(l,r) على جميع . أخرج باقي قسمة الإجابة على 10^9+7.

Examples

Example 1

Loading
Loading

Note

في الاختبار الأول، هناك المجالات التالية (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.

Scoring

  • ( نقاط): a_i فردي لجميع ، n\le 1000;

  • ( نقاط): n\le 1000;

  • ( نقاط): a_i فردي لجميع ;

  • ( نقاط): بدون قيود إضافية.